算法题 HDU Problem 2211 杀人游戏

类约瑟夫环问题

算法题目链接地址 传送门

题目要求

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1506    Accepted Submission(s): 315

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

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

Output
对于每组数据,输出最后被杀的土匪的编号。

Sample Input
1
10 3

Sample Output
10

Author
wangye

算法一

自己第一次看题目写的程序,思想很简单,觉得用数组模拟就是啦。

其实这种算法效率很低,特别是遇到这类给出的条件(N<2^31)都是整形 int 范围边缘啦。

输入 n 的值很大的话,速度超级慢。

#include<iostream>
using namespace std;

typedef struct{
	bool isKilled;
	int num;
} badGuys;

badGuys bandit[1000]; // 数组定义太大的话对于算法题目很不现实

int main(){
	int t; // t组数据
	cin >> t;
	while(t--){
		int i, count;
		int n, k; // N 个土匪,第 K 个人被杀

		cin >> n >> k;

		int currentNum = n;

		for (i = 0; i < n; i++){
			bandit[i].num = i + 1;
			bandit[i].isKilled = false;
		}

		while(currentNum != (k - 1)){
			for (i = 0, count = 1; i < n; i++){
				if (bandit[i].isKilled == false){
					if (count != k){
						count++;
					}else{
						bandit[i].isKilled = true;
						currentNum--;
						count = 1;
						if (currentNum == (k - 1))
							cout << bandit[i].num << endl;
					}
				}
			}
		}
	}
	return 0;
}

算法二

每次杀人之后,土匪的编号都是会改变的。

这个算法的思想就是使用「函数的递归调用」来模拟最后一个被杀的人在每次杀人结束后的位置,而不是像 算法一 一样的详细模拟每个人的状态。

虽然最后被取出来的人在每一次中的位置不一样,但是前一次与后一次之间存在关系。

题目所给例子「最后被杀的是 10」

  • 1 2 3 4 5 6 7 8 9 10 <