我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。
题目
以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3
号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有
2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？
本题是这个问题的升级版：已知 名玩家中有 2 人扮演狼人角色，有 2
人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？
输入格式：
输入在第一行中给出一个正整数 （
）。随后
行，第
行给出第
号玩家说的话（
），即一个玩家编号，用正号表示好人，负号表示狼人。
输出格式：
如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 和
，若存在
使得
（
），且
，则称序列
小于序列
。若无解则输出
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
思路
这道题想复杂的话可以很复杂，我觉得我的思路还是比较简单的。
先分析题意：
已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。
其实可以转化为：
- 一个狼人说谎
- 另一个狼人说真话
- 一个好人说谎
- 剩下的N-3的好人都说真话
前三个是特殊情况，由于题目规模(100)比较小，所以可以用暴力遍历的方式。所以我的思路就是：
- 用一个数组记录每个玩家说的话
records，初始化两个最小狼人编号为{100, 100} - 对两个狼人和说谎的好人设三个变量
m, n, l，进行三重遍历- 按照两个说谎的人转换两个数的符号，循环结束再复原
- 再一重遍历
i，检查可能性。检查方法很直观：- 说话内容等于假设的好人
|records[i]| != n or l，那么符号不能为负 - 说话内容等于假设的狼人
|records[i]| == n or l，那么符号不能为正 - 不符合，则标记
- 说话内容等于假设的好人
- 如果未被标记（为不可能），比较当前狼人编号
n, l是否小于已有的最小编号，
小于则更新
- 输出，如最小编号仍为
{100, 100}，即为无解
我看到的方法也都是N^4复杂度的，很多用C++的都用到了向量内积，再加三重循环，实际上也是四重循环，当然算内积应该比我的方法更快一些，写起来也更简洁。
最后我的方法时间在200ms上下，供大家参考。
代码
最新代码@github，欢迎交流
#include <stdio.h>
#include <stdlib.h>
/**
* According to the problem, we know that there will be:
* one 'good' player who lies,
* one 'bad' player who lies and
* one 'bad' pleyer who doesn't
*/
int main()
{
int N, flag, badguys[2] = {100, 100}, assum[2];
int records[101];
/* Read and update */
scanf("%d", &N);
for(int i = 1; i <= N; i++)
scanf("%d", &records[i]);
/* Assume: m and n are the players who lied */
for(int m = 1; m <= N; m++)
{ /* Assume: n and l are the 'bad' players */
for(int n = 1; n <= N; n++)
{
for(int l = 1; l <= N; l++)
{
/* only when m, n, l are not same */
if(m == n || n == l || l == m)
continue;
/* reverse */
records[m] *= -1;
records[n] *= -1;
flag = 0;
for(int i = 1; i <= N; i++)
{
/* if n or l is good or anyone else is bad, wrong! */
if(((abs(records[i]) == n || abs(records[i]) == l)
&& records[i] > 0)
|| ((abs(records[i]) != n && abs(records[i]) != l)
&& records[i] < 0))
flag = 1;
}
if(!flag)
{
assum[0] = n > l ? l : n;
assum[1] = n > l ? n : l;
/* if they are smaller */
if((assum[0] < badguys[0])
|| (assum[0] == badguys[0] && assum[1] < badguys[1]))
{
badguys[0] = assum[0];
badguys[1] = assum[1];
}
}
/* reverse back */
records[m] *= -1;
records[n] *= -1;
}
}
}
if(badguys[0] == 100 && badguys[1] == 100)
printf("No Solution");
else
printf("%d %d", badguys[0], badguys[1]);
return 0;
}
网友评论