算法题 HDU Problem 2211 杀人游戏

算法 Nov 2, 2014

类约瑟夫环问题

算法题目链接地址 传送门

题目要求

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 <

Tags

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.