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;
}