首页 > ACM题库 > HDU-杭电 > hdu 2211 杀人游戏-线性结构-[解题报告]C++
2014
01-04

hdu 2211 杀人游戏-线性结构-[解题报告]C++

杀人游戏

问题描述 :

不知道你是否玩过杀人游戏,这里的杀人游戏可没有法官,警察之类的人,只有土匪,现在已知有N个土匪站在一排,每个土匪都有一个编号,从1到N,每次杀人时给定一个K值,从还活着的土匪中,编号从小到大的找到K个人,然后杀掉,继续往下,直到找遍,然后继续从剩下的土匪中,编号从小到大找到第K个活着的土匪,然后杀掉。比如,现在有10个土匪,K为3,第一次杀掉3,6,9号的土匪,第二次杀掉4,8号土匪,第三次杀掉5号土匪,第四次杀掉7号土匪,第五次杀掉10号土匪,我们看到10号土匪是最后一个被杀掉的(从1到K-1的土匪运气好,不会被杀!)。现在给定你一个N和一个K,问你最后一个被杀掉的土匪的编号是多少。

输入:

第一行有一个T(T<=10000),接下来有T组数据,每组中包含一个N(N<2^31)和一个K(3<=K<=100&&K<N)。

输出:

第一行有一个T(T<=10000),接下来有T组数据,每组中包含一个N(N<2^31)和一个K(3<=K<=100&&K<N)。

样例输入:

1
10 3

样例输出:

10

设f(N,K)返回最后取出的编号

那么f(n,k)进行第一次选后,剩下n-n/k个人,这剩下的人里最后被取出的编号为f(n-n/k,k)记为x
那么它在前一次队列里的编号则是(x-1)/(k-1)+x
所以f(n,k)=(x-1)/(k-1)+x 其中x=f(n-n/k,k)

#include<stdio.h>
int cal(int n,int k)
{
    if(n==k)return k;
    int m=cal(n-n/k,k);
    return (m-1)/(k-1)+m;
}
int main()
{
    int _case;
    int n,k;
    scanf("%d",&_case);
    while(_case--)
    {
        scanf("%d%d",&n,&k);
        printf("%d\n",cal(n,k));
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/XDJjy/archive/2013/08/11/3251651.html


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。