目录
PAT乙级 1089 狼人杀-简单版 (20 分)
茨华上仙
2021年05月25日 11:13
收录于文集
共18篇

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，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 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解。若无解则输出 。

输入样例 1：

输出样例 1：

输入样例 2：

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

输入样例 3：

输出样例 3：

思路：

本题思路正确了代码会十分简洁，一旦你题目一遍没读懂越读理解起来会越困难。人人都知道可以穷搜，但是本题的关键在于对谁穷搜。根据题意可知只有2个狼人，而狼人有说谎但不是都说谎，换句话说就是这N个人里有1个好人说谎有1个狼人说谎。一个正确的思路是穷搜2个狼人而不是穷搜说谎者。

用数组goodMan[i]标记i号是好人（1）还是狼人（-1）。每次遍历选2个人为-1标记为狼人，然后再扫描数组统计说谎的人数和狼人的数量，若满足说谎人数=1，狼人数量=2，即为找到了一个结果（不需要你再去找另一个说谎者是谁），具体的判断方法见代码

代码块
JavaScript
自动换行
复制代码
//	https://github.com/irelia97/Study/tree/master/OJ/PAT_Basic
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> vec(N+1);

	for(int i = 1; i <= N; ++i)
		cin >> vec[i];
		
	vector<int> goodMan(N+1, 1);	//goodMan[i]==1表示i号是好人 
	int i, j;
	for(i = 1; i <= N-1; ++i){
		//	标记i号为狼 
		goodMan[i] = -1;
		for(j = i+1; j <= N; ++j){
			//	标记j号为狼 
			goodMan[j] = -1;
			//	记录说谎次数，狼人数量 
			int liesCnt = 0, wolfCnt = 0;
			
			for(int k = 1; k <= N; ++k){
				//	vec[k]表示k号认为：abs(vec[k])号是狼人(vec[k]<0) or 好人(vec[k]>0) 
				//	goodMan[abs(vec[k])]abs(vec[k])到底是狼人(-1) or 好人(1)
				//	若乘积为负说明说谎 
				if( goodMan[abs(vec[k])] * vec[k] < 0 ){
					liesCnt++;
					//	k号恰好标记为狼人 
					if( k == i || k == j )
						wolfCnt++;
				}
			}
			if( liesCnt == 2 && wolfCnt == 1 ){
				cout << i << " " << j;
				return 0;
			}
			goodMan[j] = 1;
		}
		goodMan[i] = 1;
	}
	cout << "No Solution";
	
	return 0;
}
复制成功

PAT OJ
本文为我原创，未经授权禁止转载
cv11426576