PAT乙级真题 1089 狼人杀-简单版 C++实现（假设+遍历暴力求解）_综合

题目

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？
本题是这个问题的升级版：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？
输入格式：
输入在第一行中给出一个正整数 N（5≤N≤100）。随后 N 行，第 i 行给出第 i 号玩家说的话（1≤i≤N），即一个玩家编号，用正号表示好人，负号表示狼人。
输出格式：
如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 A=a[1],…,a[M] 和 B=b[1],…,b[M]，若存在 0≤k<M 使得 a[i]=b[i] （i≤k），且 a[k+1]<b[k+1]，则称序列 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

思路

这种题没有直观的数学方法可以求解，要靠程序暴力求解，方法是假定+遍历。

由题可知：

狼人中1个说谎，1个说真话
好人中1个说谎，其余说真话

那么就假定1个说谎的狼人和1个说谎的好人记为i、j，再从剩下的人中假定一个狼人k，遍历所有组合，验证是否能成立。

把假定两个说谎者说的话变号（保证说的全是真话），判断当前数组合法需满足：

狼人有2个：除了-i、-k不能再有其它负数；
无矛盾：不存在相反数，即不能出现+i、+k；

遍历剩下的元素，找出合理的组合，记录其中最小序列，用minWolf1、minWolf2保存即可。

注意两个说谎者说的话变号后，下次遍历前要再变回来。

这个方法缺点是还需额外找最小序列。柳神的方法是：
假定两个狼人i、j，顺序遍历，这样第一次取得的组合就是最小序列；对每种狼人组合，判断所有人说的话是否满足：

说谎者有2个；
说谎者中1个狼人，1个好人；

这样代码就简洁多了，附上链接：PAT 1089 狼人杀-简单版(20 分)- 乙级_柳婼の blog-CSDN博客

代码

#include <iostream>
#include <vector>
using namespace std;int main(){int n;cin >> n;vector<int> a(n+1); //从1存储for (int i=1; i<=n; i++){cin >> a[i];}int minWolf1 = n+1;int minWolf2 = n+1;//狼人和好人各有1个说谎，用i表示说谎狼人，j表示说谎好人for (int i=1; i<=n; i++){for (int j=1; j<=n; j++){if (j==i){ //三个人序号不能重复continue;}for (int k=1; k<=n; k++){ //k表示另一个狼人if (i==k || j==k){continue;}//反转两个说谎者的话a[i] *= -1;a[j] *= -1;//遍历所有元素，验证成立需满足两点：//1.除了-i、-k不能再有其它负数；2.无矛盾：不存在相反数，即不能出现+i、+k；bool isValid = true;for (int l=1; l<=n; l++){if ((a[l]<0 && a[l]!=-i && a[l]!=-k) || (a[l]==i) || (a[l]==k)){isValid = false;break; }}//合理，保存找最小序列if (isValid){int wolf1 = min(i, k);int wolf2 = max(i, k);if (wolf1<minWolf1){minWolf1 = wolf1;minWolf2 = wolf2;}else if(wolf1==minWolf1){if (wolf2 < minWolf2){minWolf2 = wolf2;}}}//验证完复原说谎者的话a[i] *= -1;a[j] *= -1; }}}if (minWolf1 < n+1){cout << minWolf1 << " " << minWolf2 << endl;}else {cout << "No Solution" << endl;}return 0;
}