1089 狼人杀-简单版 (20分)

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？

本题是这个问题的升级版：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

输入格式：

输入在第一行中给出一个正整数 N（5）。随后 N 行，第 i 行给出第 i 号玩家说的话（1），即一个玩家编号，用正号表示好人，负号表示狼人。

输出格式：

如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 [ 和 [，若存在 0 使得 [ （i≤k），且 [，则称序列 A 小于序列 B。若无解则输出 No Solution。

输入样例 1： 

5
-2
+3
-4
+5
+4

输出样例 1： 

1 4

输入样例 2： 

6
+6
+3
+1
-5
-2
+4

输出样例 2（解不唯一）： 

1 5

输入样例 3： 

5
-2
-3
-4
-5
-1

输出样例 3： 

No Solution
			

				
			


#include<iostream>
#include<vector>
using namespace std;
int main()
{
	FILE* st;
	freopen_s(&st, "input.txt", "r", stdin);
	int n;
	while (cin >> n)
	{
		vector<int>v(n + 1);
		for (int i = 1; i <= n; i++)
			cin >> v[i];
		vector<int>lie;
		int flag = 0;
		for (int i = 1; i <= n; i++)//假设全部人都是好人，然后这个外两重循环的意思是，从n个人中取2个人假设他们是狼人例如（1,2），或（1，3）,这个两层循环保证这个集合不重复
		{
			for (int j=i+1; j <= n; j++)
			{
				vector<int>a(n + 1, 1);//假设全部人都是好人
				a[i] = a[j] = -1;//从n个人中取2个人假设他们是狼人
				lie.clear();
				for (int k = 1; k <= n; k++)//然后从头遍历，看他说的话和假设的事实是否矛盾，因为好人为1，狼人为-1，a[abs[v[k]]即为V[K]说的这个人的真实情况
				{//V[k]只有两种情况 >0和<0,例如 当V[K]=-2,即第2个人是狼人，真实情况储存在a数组中，查看a[2]=-2,两者相同 乘积>0，没说谎，如果a[2]=2，乘积<0，k说谎了，加入说谎lie数组
					if (v[k] * a[abs(v[k])] < 0)
						lie.push_back(k);
				}
				if (lie.size() == 2 && a[lie[0]] + a[lie[1]] == 0)//两个人说谎，且必须是一好人一狼人 好人=1，狼人=-1
				{
					flag = 1;
					cout << i << " " << j << endl;//输出此时假设的下标，因为我们是从1开始遍历的，此时即为最小序列，遍历到就直接跳出，不需要再遍历了
					break;
				}
			}
			if (flag == 1)//遍历到就直接跳出
				break;
		}
		if(flag==0)//没遍历到就直接跳出
			cout << "No Solution" << endl;
	}
	return 0;
}
总结：此道狼人杀的问题，关键点在题目给出的要求： 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎，所以我们不必要跟自己玩推理游戏一样，只需要依次假设狼人是谁，然后根据此时假设的事实，统计撒谎人的个数和撒谎人的身份，个数要=2，且一狼人，一好人，不符合就进行下一组合的狼人假设，所以题目给出了判定条件 要学会提取
和1065的单身狗题，有一点点类似