PAT-A1148/B1089 Werewolf - Simple Version 狼人杀

Werewolf（狼人杀） is a game in which the players are partitioned into two parties: the werewolves and the human beings. Suppose that in a game,

player #1 said: "Player #2 is a werewolf.";
player #2 said: "Player #3 is a human.";
player #3 said: "Player #4 is a werewolf.";
player #4 said: "Player #5 is a human."; and
player #5 said: "Player #4 is a human.".

Given that there were 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liers. Can you point out the werewolves?

Now you are asked to solve a harder version of this problem: given that there were $N$ players, with 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liers. You are supposed to point out the werewolves.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N$ ( $5 \leq N \leq 100$ ). Then $N$ lines follow and the $i$ -th line gives the statement of the $i$ -th player ( $1 \leq i \leq N$ ), which is represented by the index of the player with a positive sign for a human and a negative sign for a werewolf.

Output Specification:

If a solution exists, print in a line in ascending order the indices of the two werewolves. The numbers must be separated by exactly one space with no extra spaces at the beginning or the end of the line. If there are more than one solution, you must output the smallest solution sequence -- that is, for two sequences $A = a [1], . . ., a [M]$ and $B = b [1], . . ., b [M]$ , if there exists $0 \leq k < M$ such that $a [i] = b [i]$ ( $i \leq k$ ) and $a [k + 1] < b [k + 1]$ , then $A$ is said to be smaller than $B$ . In case there is no solution, simply print No Solution.

Sample Input 1:

5
-2
+3
-4
+5
+4

Sample Output 1:

1 4

Sample Input 2:

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

Sample Output 2 (the solution is not unique):

1 5

Sample Input 3:

5
-2
-3
-4
-5
-1

Sample Output 3:

No Solution

题目大意：

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

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

输入格式：

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

输出格式：

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

这道题用到了贪心算法，解题的思路是，将所有的两个人的组合（例如5个人就是12,13,14,15,23,24,25,34,35,45）都遍历一遍，假设这两个人是狼人，然后遍历输入的口供，如果恰好是两个人撒谎、而且这两个人有且只有一个狼人，这就是一个满足题目要求的组合。由于从前往后遍历，所以第一个发现的组合就是最小的，直接return就好。

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

int main(){
  int cnt;
  cin >> cnt;
  vector<int> I(cnt + 1);
  for(int i = 1; i <= cnt; i++)
    cin >> I[i];
    //-2 +3 -4 +5 +4 
  for(int i = 1; i < cnt; i++){
    for(int j = i + 1; j <= cnt; j++){
      vector<int> tmp(cnt + 1), lier; 
      //生成i和j为狼人时的序列 
      for(int p = 1; p <= cnt; p++)
        tmp[p] = p;
      //假定此时i和j是狼人 
      tmp[i] *= -1, tmp[j] *= -1; 
      for(int _ = 1; _ <= cnt; _++){
        //能在刚刚生成的序列中找到这个数字，说明它没有说谎 
        if(find(tmp.begin(), tmp.end(), I[_]) == tmp.end()){
          //发现说谎，丢进容器 
          lier.push_back(_);
        }
      }
      //恰好两个人说谎，而且两个人一正一负（一好人一狼人） 
      if(lier.size() == 2 && tmp[lier[0]] * tmp[lier[1]] < 0){
        cout << i << ' ' << j;
        return 0;  
      }
    }
  }
  cout << "No Solution";
  return 0;
}

斐斐のBlog