ybt1418：猴子选大王

时间限制: 500 ms         内存限制: 65536 KB
提交数: 3454     通过数: 711

由经典约瑟夫问题改成。

有NN个猴子，编号从11到NN。每个猴子对应一个正整数XiXi,表示如果从编号为ii的猴子开始报数，需要数到XiXi。

这NN个猴子围成一圈，从第一个开始报数，数到第11个猴子对应的正整数X1X1的猴子出队，然后从它的下一位继续从11开始报数，数到对应的XiXi时出队，如此循环直到剩下一个猴子，最后剩下的那个猴子就是猴子们选出的大王。

例如：

N=5,XiN=5,Xi对应为：1，2，3，4，51，2，3，4，5。

出队的顺序为：1，3，4，51，3，4，5。

第一行为NN;

第二行为NN个小于等于100100的正整数。对应于从某个猴子位置开始报数，需要报数的次数。

被选为大王的猴子的编号。

5
1 2 3 4 5

2

【提示】

【数据范围】

N≤1000000

#include 
#define N 100005
#define ll long long
#define ull unsigned long long
#define il inline
#define rg register
using namespace std;
int a[N * 10];
int main()
{
    cin.sync_with_stdio(false);//输入加速
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    deque q;
    for (int i = 1; i <= n; i++)
        q.push_back(i);
    while (q.size() > 1)//猴子数多与一个
    {
        int now = a[q.front()];//表示要数到几
        for (int i = 1; i < now; i++)//前now-1个不变
        {
            q.push_back(q.front());
            q.pop_front();
        }
        q.pop_front();//最后一个出队
    }
    cout << q.front() << endl;//最后剩下的猴子是大王
    system("pause");
    return 0;
}