4415: [Shoi2013]发牌
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 173 Solved: 124
[Submit][Status][Discuss]
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是牌库中唯一的一张牌。
Input
第1行,一个整数N,表示牌的数量。第2行到第N + 1行,在第i + 1行,有一个整数R_i, 0≤R_i<N
Output
第1行到第N行:第i行只有一个整数,表示玩家收到的第i张牌的编号。
Sample Input
4
2
0
3
2
2
0
3
2
Sample Output
3
4
2
1
4
2
1
HINT
N<=70万
最自然的思想:在树状数组中跑二分。
k的意义是当前n个数字中的答案是第几大的。 O(nlogn^2)迷之水过
(当然可以改成线段树,这样就不要二分了,哪边符合往哪边走O(nlogn))
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);
#define llg long long
#define maxn 700010
llg i,j,k,x,n,m,T,y,l,r,c[maxn];
using namespace std;
llg lowbit(llg x) {return x&-x;}
void add(llg x,llg val){while (x<=y) {c[x]+=val; x+=lowbit(x);}}
llg sum(llg x) {llg ans=; while (x>) {ans+=c[x]; x-=lowbit(x);} return ans;}
int main()
{
yyj("a");
cin>>n; y=n;
for (i=;i<=n;i++) add(i,);
k=;
while (n--)
{
scanf("%lld",&m);
k=(k+m-)%(n+)+;
l=; r=y;
while (l!=r)
{
llg mid=(l+r)/;
llg w=sum(mid);
if (w>=k) r=mid; else l=mid+;
}
printf("%lld\n",l);
add(l,-);
//k++;
}
return ;
}
倒数第二还有谁?