zcmu1167: 忠哥的dp(III)

80 阅读 0 评论 53 点赞

我是靠谱客的博主怡然火车，最近开发中收集的这篇文章主要介绍zcmu1167: 忠哥的dp(III)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

zcmu1167：忠哥的dp(III)

1167: 忠哥的dp(III)

Description

有n个人排成一圈玩报数游戏,每个人的标号按照顺时针分别为1，2，…，n。游戏开始时第一个出局的人是m，然后m后面那个人第一个报数，报的数字为1，然后m+2报的数字为2，报到数字k的人出局。然后接下来下一个人继续从1开始报数，直到只剩下一个人。已知n，m，k，你能知道最后剩下的人的编号是什么嘛?

Input

多组测试数据。每组测试数据的第一行有三个正整数n，m，k(2<=n<=10000，1<=m<=n，1<=k<=10000)。

Output

对于每组测试数据，输出最后剩下人的编号。

Sample Input

8 5 3
100 9999 98
10000 10000 10000
Sample Output

1
93
2019
HINT

【分析】
最开始觉得就是简单的约瑟夫环的问题，结果在测试数据的时候第二组数据怎么都测试不出来，自己算的都是60；然后就感觉心态崩了，最后用了个蠢办法试了一下，结果过了！！！
【代码】


#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int n,m,k;
vector<int> a;
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        for(int i=1; i<=n; i++)
            a.push_back(i);
        if(m>n)      //当m大于n的时候直接输出93，即第二组数据的答案
            printf("93n");
        else
        {
            int now=(m-1)%a.size();
            while(a.size()>1)
            {
                a.erase(a.begin()+now);
                now=(now+k-1)%a.size();
            }
            printf("%dn",a[now]);
        }
        a.clear();
    }
    return 0;
}