題目傳送：Buy Tickets
思路：線段樹，從後往前依次插入，插入一個更新一次
AC代碼：
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; const int maxn = 200005; struct node { int pos, v; }a[maxn]; int x[maxn << 2], num[maxn]; void build(int l, int r, int rt) { x[rt] = r - l + 1; if(r == l) return; int mid = (r + l) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); } int query(int p, int l, int r, int rt) { x[rt] --; if(l == r) return l; int mid = (l + r) >> 1; if(x[rt << 1] >= p) return query(p, l, mid, rt << 1); else return query(p - x[rt << 1], mid + 1, r, rt << 1 | 1); } int main() { int n; while(scanf("%d", &n) != EOF) { for(int i = 1; i <= n; i ++) { scanf("%d %d", &a[i].pos, &a[i].v); } build(1, n, 1); for(int i = n; i >= 1; i --) { int p = query(a[i].pos + 1, 1, n, 1); num[p] = a[i].v; } for(int i = 1; i < n; i ++) { printf("%d ", num[i]); } printf("%d\n", num[n]); } return 0; }
【C++探索之旅】第一部分第十課之文件讀寫，海闊憑魚躍
UVA - 111 - History Grading
leetcode筆記：Unique Paths 一. 題
OpenCL之簡單的向量加法實現 向量加法 程序流程 創
hdu 5071 Chat(模擬|Splay) Ch
nyoj-無線網絡覆蓋 無線網絡覆蓋 時間限制：300
