POJ 2828 Buy Tickets（树状数组）
最后更新于：2022-04-01 15:53:09
题目链接：[点击打开链接](http://poj.org/problem?id=2828)
题意：给n个人依次插队的情况， 要求求出最终的队伍情况。
该题可以用树状数组很方便的维护。
如果从前向后扫的话， 每次插队都会影响这个人后面的情况， 所以我们可以倒着进行， 那么最后一个人的位置就是最终位置， 对于前面的人的位置， 只受后面人的影响， 所以等价于其最终位置是第pos[i]+1个空位。 那么也就是说要快速的找到第pos[i]+1个空位。 显然， 这又可以用二分位置和树状数组维护的方法来优化算法。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 200000 + 10;
int T,n,m,bit[maxn],ans[maxn];
struct node {
int pre, v;
}a[maxn];
int sum(int x) {
int ans = 0;
while(x > 0) {
ans += bit[x];
x -= x & -x;
}
return ans;
}
void add(int x, int d) {
while(x <= n) {
bit[x] += d;
x += x & -x;
}
}
int main() {
while(~scanf("%d",&n)) {
memset(bit, 0, (n+1)*sizeof(bit[0]));
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].pre,&a[i].v);
for(int i=n;i>=1;i--) {
int l = 1, r = n, mid;
while(r > l) {
mid = (l + r) >> 1;
if(mid - sum(mid) > a[i].pre) r = mid;
else l = mid + 1;
}
ans[l] = a[i].v;
add(l, 1);
}
printf("%d",ans[1]);
for(int i=2;i<=n;i++) printf(" %d",ans[i]);
printf("\n");
}
return 0;
}
~~~