题目链接：1089 狼人杀-简单版 (20 point(s))
题目描述
以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，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
Java代码
/**********************************************************************************
Submit Time Status Score Problem Compiler Run Time User
7/28/2019, 12:32:52 Accepted 20 1089 Java (openjdk) 80 ms wowpH
**********************************************************************************/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
// w1,w2是狼，word是玩家说的话
private static boolean judge(int w1, int w2, int word) {// 判断是否是真话
if (word < 0 && (0 == word + w1 || 0 == word + w2)) {
return true; // 语义：某位玩家是狼，并且他真的是狼
} else if (word > 0 && word != w1 && word != w2) {
return true; // 语义：某位玩家是人，并且他真的是人
}
return false; // 否则是谎话
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // 玩家人数
int[] word = new int[n + 1]; // 玩家说的话
for (int i = 1; i <= n; ++i) {
word[i] = Integer.parseInt(br.readLine());
}
boolean find = false; // 初始未找到狼
for (int i = 1; i < n && !find; ++i) { // 假设第i位是狼，且未找到狼
for (int j = i + 1; j <= n && !find; ++j) { // 假设第j位是狼，且未找到狼
boolean word1 = judge(i, j, word[i]); // i说的话
boolean word2 = judge(i, j, word[j]); // j说的话
if (word1 && !word2 || !word1 && word2) {// 一真一假
int liePeopleNum = 0; // 说谎的“好人”数
// 遍历“好人”，找到说谎的“好人”数
for (int k = 1; k <= n && liePeopleNum <= 1; ++k) {
if (k != i && k != j && !judge(i, j, word[k])) {
++liePeopleNum; // k(“好人”)说假话，说谎的“好人”数加1
}
}
if (1 == liePeopleNum) { // 有且仅有一个“好人”说谎
find = true; // 已找到
System.out.println(i + " " + j);// i和j是狼
}
}
}
}
if (false == find) {
System.out.println("No Solution"); // 未找到，无解
}
}
}
版权声明
- 转载、参考、引用必须在首页添加如下文字：
[PAT(B) 1089 狼人杀-简单版（Java）逻辑推理—wowpH](https://blog.****.net/pfdvnah/article/details/97613402) - 代码原创，公开引用不能删除首行注释（作者，版本号，时间等信息）；
- 如果有疑问欢迎评论区留言，尽量解答；
- 如果有错误，还望大侠评论区指正。