[SHOI2013]发牌

假设一开始，荷官拿出了一副新牌，这副牌有N张不同的牌，编号依次为1到N。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为1, 2,……直到N，N号牌在牌库底。为了发完所有的牌，荷官会进行N次发牌操作，在第i次发牌之前，他会连续进行R_i次销牌操作，R_i由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？

举个例子，假设N = 4，则一开始的时候，牌库中牌的构成顺序为{1, 2, 3, 4}。假设R₁=2，则荷官应该连销两次牌，将1和2放入牌库底，再将3发给玩家。目前牌库中的牌顺序为{4, 1, 2}。假设R₂=0，荷官不需要销牌，直接将4发给玩家，目前牌库中的牌顺序为{1,2}。假设R₃=3，则荷官依次销去了1, 2, 1，再将2发给了玩家。目前牌库仅剩下一张牌1。假设R₄=2，荷官在重复销去两次1之后，还是将1发给了玩家，这是因为1是牌库中唯一的一张牌。

#include<bits/stdc++.h> using namespace std; #define maxm 700020 int c[maxm],n; int lowbit(int i) { return i&-i; } void add(int i,int t) { while(i<=n) { c[i]+=t; i+=lowbit(i); } } int ask(int i) { int ans=0; while(i) { ans+=c[i]; i-=lowbit(i); } return ans; } int main() { cin .tie(0); cout.tie(0); cin >> n; for(int i=1;i<=n;i++) { add(i,1); } int now=1; for(int i=n;i>=1;i--) { int x; cin >> x; now=(now+x)%i; if(now==0) now=i; int l=1,r=n; int ans=0; while(l<=r) { int mid=(l+r)/2; if(ask(mid)>=now) { ans = mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); add(ans,-1); } return 0; }

详情