还是线段树……题目是N个人站成一个环进行N轮的筛人，每轮都筛走一个人，第i轮筛走的人得到f(i)颗糖，要求最先得到最多糖的人。第一个被筛的人为k，每次某人被筛，都会给出下一个被筛的人相对当前位置的偏移量（顺时针方向）ai，ai!=0且|ai|<10^8。 其实知道要用线段树之后，题目就很简单了……k值的维护可以通过剩余人数n-i和a[i]求出，然后每轮筛去还在环中的第k个人即可，用线段树可以log(n)得到每轮被筛的人的编号。但这题竟然卡的是求f(i)。。。换了两种方法求f(i)都超时后便老老实实打表了。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<cstdio> int n,k,d,di,a[500001],ml; char s[500001][11]; struct node { char b; int d; node *l,*r; }mem[2000000],*root; void init(int n) { if(n<2) d=di=1; else if(n<4) d=di=2; else if(n<6) d=4,di=3; else if(n<12) d=6,di=4; else if(n<24) d=12,di=6; else if(n<36) d=24,di=8; else if(n<48) d=36,di=9; else if(n<60) d=48,di=10; else if(n<120) d=60,di=12; else if(n<180) d=120,di=16; else if(n<240) d=180,di=18; else if(n<360) d=240,di=20; else if(n<720) d=360,di=24; else if(n<840) d=720,di=30; else if(n<1260) d=840,di=32; else if(n<1680) d=1260,di=36; else if(n<2520) d=1680,di=40; else if(n<5040) d=2520,di=48; else if(n<7560) d=5040,di=60; else if(n<10080) d=7560,di=64; else if(n<15120) d=10080,di=72; else if(n<20160) d=15120,di=80; else if(n<25200) d=20160,di=84; else if(n<27720) d=25200,di=90; else if(n<45360) d=27720,di=96; else if(n<50400) d=45360,di=100; else if(n<55440) d=50400,di=108; else if(n<83160) d=55440,di=120; else if(n<110880) d=83160,di=128; else if(n<166320) d=110880,di=144; else if(n<221760) d=166320,di=160; else if(n<277200) d=221760,di=168; else if(n<332640) d=277200,di=180; else if(n<498960) d=332640,di=192; else d=498960,di=200; } inline int ins(int i) { int L=0,R=n-1,m,e=k; node *p=root; while(1) { p->d++; m=L+R>>1; if(L==R) break; if(p->b) { p->b=0; p->l=&mem[ml++]; p->l->b=1; p->l->d=0; p->r=&mem[ml++]; p->r->b=1; p->r->d=0; } if(e<=m-L-p->l->d) { p=p->l; R=m; } else { e-=1+m-L-p->l->d; p=p->r; L=m+1; } } if(i<n-1) { if(a[m]>0) --k; a[m]%=n-1-i; a[m]+=n-1-i; k+=a[m]; k%=n-1-i; } return m; } int main() { int i,j; while(~scanf("%d%d",&n,&k)) { init(n); ml=0; k--; root=&mem[ml++]; root->b=1; root->d=0; for(i=0;i<n;i++) scanf("%s%d",s[i],&a[i]); for(i=0;i<d;i++) j=ins(i); printf("%s %d\n",s[j],di); } return 0; } |