题目

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

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

输入格式：

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

输出格式：

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

输入样例 1：

1
2
3
4
5
6

5
-2
+3
-4
+5
+4

输出样例 1：

1

1 4

输入样例 2：

1
2
3
4
5
6
7

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

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

1

1 5

输入样例 3：

1
2
3
4
5
6

5
-2
-3
-4
-5
-1

输出样例 3：

1

No Solution

思路

这道题想复杂的话可以很复杂，我觉得我的思路还是比较简单的。

先分析题意：

已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。

其实可以转化为：

数量 好人 狼人
说谎 1 1
说真话 N-3 1

有三个是特殊情况，由于题目规模(100)比较小，所以可以用暴力遍历的方式。所以我的思路就是：

  • 用一个数组记录每个玩家说的话records，初始化两个最小狼人编号为{100, 100}
  • 对两个狼人和说谎的好人设三个变量m, n, l，进行三重遍历
    • 按照两个说谎的人转换两个数的符号，循环结束再复原
    • 再一重遍历i，检查可能性。检查方法很直观：
      • 说话内容等于假设的好人abs(records[i]) != n or l，那么符号不能为负
      • 说话内容等于假设的狼人abs(records[i]) == n or l，那么符号不能为正
      • 不符合，则标记
    • 如果未被标记（为不可能），比较当前狼人编号n, l是否小于已有的最小编号， 小于则更新
  • 输出，如最小编号仍为{100, 100}，即为无解

我看到的方法也都是N^4复杂度的，很多用C++的都用到了向量内积，再加三重循环，实际上也是四重循环，当然算内积应该比我的方法更快一些，写起来也更简洁。

最后我的方法时间在200ms上下，供大家参考。

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#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;
}