Loading... ## 树状数组 <!--more--> 我们可以倒序枚举,然后求解答案。显然最后一个人的位置是$a[n] + 1$, 这个位置已经有人了,然后我们把这个位置删去。我们可以发现每个人的位置就是$1-n$中未被使用的位置中第$a[i] + 1$个数,我们可以用树状数组来维护位置每个位置的使用情况,我们每次查询既是查询最小的$pos$,使得$sum[pos]>=a[i]+1$ (sum是前缀和),这个可以用树状数组+二分来解决,复杂度 $O(n*log^2_n)$ ,不过我们可以利用树状数组的性质,用倍增来处理查询。 我们都知道树状数组$c[i]$代表原数组中 $a[i-lowbit(i)+1,i]$ 的和,我们也知道一个数可以拆分成若干个二进制的和。所以我们用倍增思想来找到 $<a[i]+1$ 的最大的数x,注意这里一定要写小于,最终x+1就是答案。复杂度$O(n*log_n)$。 虽然复杂度差个log,但是跑起来时间差不多,23333. ```cpp #include<cstdio> using namespace std; #define lowbit(x) (x&(-x)) const int N=2e5+10; int a[N],n,c[N],b[N],ans[N]; int up = 20; void add(int x,int val) { while(x<=n) { c[x]+=val; x+=lowbit(x); } } int ask(int x) { int res=0; while(x) { res+=c[x]; x-=lowbit(x); } return res; } int query(int k) { int sum = 0 ,ans =0; for(int i = up ; i>=0 ;--i) { if(ans + (1<<i) <= n && sum + c[ans + (1<<i)] < k ) { ans += (1<<i) ; sum += c[ans] ; } } return ans + 1; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); add(i,1); } for(int i=n;i>=1;i--) { int pos=query(a[i]+1); ans[pos]=b[i]; add(pos,-1); } for(int i=1;i<=n;i++) printf("%d ",ans[i]); puts(""); for(int i = 0;i<=n;++i) c[i] = 0; } return 0; } ```` Last modification:November 14th, 2019 at 05:22 pm © 允许规范转载 Support 如果觉得我的文章对你有用,请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat