1418:猴子选大王
时间限制: 500 ms 内存限制: 65536 KB
提交数: 2046 通过数: 440
【题目描述】
由经典约瑟夫问题改成。
有N个猴子,编号从1到N。每个猴子对应一个正整数Xi,表示如果从编号为i的猴子开始报数,需要数到Xi。
这N个猴子围成一圈,从第一个开始报数,数到第1个猴子对应的正整数X1的猴子出队,然后从它的下一位继续从1开始报数,数到对应的Xi时出队,如此循环直到剩下一个猴子,最后剩下的那个猴子就是猴子们选出的大王。
例如:
N=5,Xi对应为:1,2,3,4,5。
出队的顺序为:1,3,4,5。
【输入】
第一行为N;
第二行为N个小于等于100的正整数。对应于从某个猴子位置开始报数,需要报数的次数。
【输出】
被选为大王的猴子的编号。
【输入样例】
5
1 2 3 4 5
【输出样例】
2
【提示】
【数据范围】
N≤1000000
数据量略大,用链表完成,并且用伪动态分配内存法.
#include <iostream> #include <cstdio> #define NEW() &memlake[N++] using namespace std; struct node { node *last; node *next; int num; int k; }; node memlake[1000010]; //内存池 int N=0; int main() { int n; cin>>n; //int n=1000000; node* mok=NEW(); for(int i=1; i<=n; i++) { scanf("%d",&mok->num); mok->k=i; mok->next=NEW(); mok->next->last=mok; mok=mok->next; } mok->last->next=&memlake[0]; memlake[0].last=mok->last; mok=&memlake[0]; while(mok->last!=mok) { int t=mok->num; while(--t) mok=mok->next; //cout<<mok->k; mok->last->next=mok->next; mok->next->last=mok->last; mok=mok->next; } cout<<mok->k; return 0; }