ReZero's Utopia.

击鼓传花

字数统计: 307阅读时长: 1 min
2016/11/02 Share

就是转圈题
要么链表,要么取余

设有N个人围成一个圈,每人手里都握着一个令牌写明一个数字(随机生成的)。从第一个人开始玩“击鼓传花”游戏,第一个击的次数为其令牌上写明的数字数(假设为m1)。第m1个人出列。下次再从第m1+1个人开始新的“击鼓传花”击的次数也为其令牌上写明的次数,等于该次数的人出列。重复以上过程直到所有人都出列为止。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct node{
    int index;
    int data;
}node;

int main(){
    int cases;
    cin >> cases;
    for(int kase = 1; kase <= cases; ++kase){
        cout << "Case #"<< kase <<":" << endl;
        vector<node> cir;
        int m;  cin >> m;
        for(int i = 1; i <= m; ++i){
            node t;  cin >> t.data;
            t.index = i;
            cir.push_back(t);
        }

        int temp, loop;
        temp = cir[0].data;
        loop = temp % cir.size();
        cout << cir[loop].index;
        cir.erase(cir.begin() + loop);

        for(int i = 2; i < m; i++)
        {
            temp = cir[loop % cir.size()].data;
            loop = ((loop % cir.size()) + temp) % cir.size();
            cout << " " << cir[loop].index;
            cir.erase(cir.begin() + loop);
        }
        cout << endl;
    }
}

/**************************************************************
    Problem: 1682
    User: 201501060807
    Language: C++
    Result: Accepted
    Time:1124 ms
    Memory:1528 kb
****************************************************************/
CATALOG