[BZOJ 4415][Shoi2013]发牌（树状数组+二分）
Description
假设一开始，荷官拿出了一副新牌，这副牌有N张不同的牌，编号依次为1到N。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为1, 2,……直到N，N号牌在牌库底。为了发完所有的牌，荷官会进行N次发牌操作，在第i次发牌之前，他会连续进行R_i次销牌操作，R_i由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？
举个例子，假设N = 4，则一开始的时候，牌库中牌的构成顺序为{1, 2, 3, 4}。
假设R1=2，则荷官应该连销两次牌，将1和2放入牌库底，再将3发给玩家。目前牌库中的牌顺序为{4, 1, 2}。
假设R2=0，荷官不需要销牌，直接将4发给玩家，目前牌库中的牌顺序为{1,2}。
假设R3=3，则荷官依次销去了1, 2, 1，再将2发给了玩家。目前牌库仅剩下一张牌1。
假设R4=2，荷官在重复销去两次1之后，还是将1发给了玩家，这是因为1是牌库中唯一的一张牌。
Solution
学习了一下怎么在树状数组上二分…
大概就是查询完第k大的数（每次洗牌的时候算一下这个k）之后就把这个数删掉
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define MAXN 700005 using namespace std; int n,c[MAXN]; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar(); } return x*f; } int lowbit(int x){return x&-x;} void build() { for(int i=1;i<=n;i++) { c[i]++; if(i+lowbit(i)<=n)c[i+lowbit(i)]+=c[i]; } } int solve(int sum) { int x=0,now=0; for(int i=(1<<22);i;i>>=1) { if(x+i<=n&&now+c[x+i]<sum) now+=c[x+i],x+=i; } ++x; for(int i=x;i<=n;i+=lowbit(i))c[i]--; return x; } int query(int pos) { int res=0; while(pos>0) {res+=c[pos];pos-=lowbit(pos);} return res; } int main() { n=read();build(); int now=1; for(int i=n;i>0;i--) { int r=read(); now+=r,now%=i; if(!now)now+=i; printf("%d\n",solve(now)); } return 0; }
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。