时间限制: 500 ms 内存限制: 65536 KB
【题目描述】
由经典约瑟夫问题改成。
有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
1. #include <bits/stdc++.h> 2. using namespace std; 3. void readint(int &data) { 4. char ch = getchar(); 5. while (ch < '0' || ch > '9') ch = getchar(); 6. data = 0; 7. do{ 8. data = data*10 + ch-'0'; 9. ch = getchar(); 10. }while (ch >= '0' && ch <= '9'); 11. } 12. int n, a[1000050], cnt, m; 13. 14. int main() 15. { 16. cin >> n; 17. queue <int> q; 18. for(int i=1;i<=n;i++) 19. { 20. //scanf("%d",&a[i]); 21. readint(a[i]); 22. q.push(i); 23. } 24. //for(int i = 1; i <= n; i++) { 25. // cin >> a[i]; 26. // q.push(i); //入队 27. // } 28. m = a[1]; // 第一个要求的数其实就是a[1] 29. while (q.size() != 1) { 30. ++cnt; // 报数 31. int x = q.front(); 32. q.pop(); 33. if (cnt != m) q.push(x); // 若没到要求的数，则入队，继续报数 34. else { // 同循环队列 35. cnt = 0; 36. m = a[q.front()]; // 出队，并更换m 37. } 38. } 39. cout << q.front() << endl; 40. return 0; 41. } 42. /* 43. 5 44. 1 2 3 4 5 45. */
