首页 > 代码库 > POJ 2886 Who Gets the Most Candies(线段树+约瑟夫环)
POJ 2886 Who Gets the Most Candies(线段树+约瑟夫环)
题目链接:POJ 2886 Who Gets the Most Candies
【题目】N个孩子顺时针坐成一个圆圈,从1~N编号,每个孩子手中有一张标有非零整数的卡片。第K个孩子先出圈,如果他手中卡片上的数字A>0,下一个出圈的是他左手边第A个孩子。A<0,下一个出圈的是他右手边第(-A)个孩子。第p个出圈的孩子会得到F(p)个糖果,F(p)为p的因子数。输出得到糖果数最多的孩子的名字及糖果数目。
【思路】孩子数目很大(1~500000),于是想到要用线段树来优化,然后就是模拟出圈过程。并更新最大糖果数目。然后因为是一个圈,编号就每次都要取模,因为取模结果总是0~num-1,而编号确实1~num,所以取模要编号K-1,求出结果后再K+1。
①A>0, 因为这个人出去了,那么后面的人的编号都会先减一所以这里的要K-2。于是下一个出圈的就应该是剩余孩子中的第((K-2+A)%num+num)%num+1个。
②A<0,因为这个人出去,对前面的人是没有影响的。于是下一个出圈的就应该是剩余孩子中的第((K-1+A)%num+num)%num+1个。
这里的F(p)我是直接数组暴力打表得来的,最后1500MS过了,看网上有一种反素数,更加快,有空去学。
【涨姿势】代码中注释的地方在问了学长之后搞明白了,有负数的时候必须模两次,比如-14%6,(-14+6)%6和((-14)%6+6)%6的结果是不一样的,也就是说n%k,当n大于k的负两倍时,第一次模能够让它保证值落在-1倍~1倍之间,第二次模让它变成正数。
下面贴代码:
1 /* 2 ** POJ 2886 Who Gets the Most Candies 3 ** Created by Rayn @@ 2014/05/09 4 ** 线段树 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 #include <algorithm> 10 using namespace std; 11 const int MAX = 500100; 12 13 struct Child { 14 char name[12]; 15 int A; 16 } child[MAX]; 17 18 int n, k, tree[MAX<<2], candy[MAX]; 19 20 void GetCandy() //计算约数 21 { 22 memset(candy, 0, sizeof(candy)); 23 int limit = (int)sqrt(MAX); 24 for(int i=1; i<limit; ++i) 25 { 26 for(int j=i+1; j*i<MAX; ++j) 27 { 28 candy[i*j] += 2; 29 } 30 candy[i*i]++; 31 } 32 /* 33 for(int i=1; i<=50; ++i) 34 printf("candy[%d]: %d\n",i, candy[i]); 35 printf("\n"); 36 //*/ 37 } 38 void BuildTree(int rt, int l, int r) 39 { 40 tree[rt] = r - l + 1; 41 if(l == r) 42 { 43 return ; 44 } 45 int mid = (l + r) >> 1; 46 BuildTree(rt<<1, l, mid); 47 BuildTree(rt<<1|1, mid+1, r); 48 } 49 int Update(int rt, int l, int r, int val) 50 { 51 tree[rt]--; 52 if(l == r) 53 { 54 return l; 55 } 56 int ans, mid = (l + r) >> 1; 57 if(val <= tree[rt<<1]) 58 ans = Update(rt<<1, l, mid, val); 59 else 60 ans = Update(rt<<1|1, mid+1, r, val-tree[rt<<1]); 61 tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 62 return ans; 63 } 64 int main() 65 { 66 #ifdef _Rayn 67 //freopen("in.txt", "r", stdin); 68 #endif 69 70 GetCandy(); 71 while(scanf("%d%d", &n, &k) != EOF) 72 { 73 memset(tree, 0, sizeof(tree)); 74 BuildTree(1, 1, n); 75 for(int i=1; i<=n; ++i) 76 { 77 scanf("%s%d", child[i].name, &child[i].A); 78 } 79 int maxVal = -1, maxPos, pos; 80 int num = n; 81 for(int i=1; i<=n; ++i) 82 { 83 pos = Update(1, 1, n, k); 84 num--; 85 if(candy[i] > maxVal) 86 { 87 maxVal = candy[i]; 88 maxPos = pos; 89 } 90 91 if(num == 0) 92 break; 93 /* 94 ** 因为取模结果总是0~num-1,所以取模要编号k-1,求出结果后再+1。 95 ** A>0, 因为这个人出去了,那么后面的人的编号都会先减一 96 ** 所以这里的k要再-1。 97 ** A<0,因为这个人出去,对前面的人是没有影响的。 98 */ 99 if(child[pos].A > 0) 100 { 101 k = ((k-2 + child[pos].A) % num + num) % num + 1; 102 } 103 else 104 { 105 //为何模两次就对了呢 106 //k = ((k-1 + child[pos].A + num) % num + 1; 107 k = ((k-1 + child[pos].A) % num + num) % num + 1; 108 } 109 } 110 printf("%s %d\n", child[maxPos].name, maxVal); 111 } 112 return 0; 113 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。