以下文字摘自《灵机一动. 好玩的数学》:"狼人杀" 游戏分为狼人, 好人两大阵营. 在一局 "狼人杀" 游戏中, 1 号玩家说:"2 号是狼人",2 号玩家说:"3 号是好人",3 号玩家说:"4 号是狼人",4 号玩家说:"5 号是好人",5 号玩家说:"4 号是好人". 已知这 5 名玩家中有 2 人扮演狼人角色, 有 2 人说的不是实话, 有狼人撒谎但并不是所有狼人都在撒谎. 扮演狼人角色的是哪两号玩家?
本题是这个问题的升级版: 已知 N 名玩家中有 2 人扮演狼人角色, 有 2 人说的不是实话, 有狼人撒谎但并不是所有狼人都在撒谎. 要求你找出扮演狼人角色的是哪几号玩家?
输入格式:
输入在第一行中给出一个正整数 N(5). 随后 N 行, 第 i 行给出第 i 号玩家说的话 (1), 即一个玩家编号, 用正号表示好人, 负号表示狼人.
输出格式:
如果有解, 在一行中按递增顺序输出 2 个狼人的编号, 其间以空格分隔, 行首尾不得有多余空格. 如果解不唯一, 则输出最小序列解 -- 即对于两个序列 [和 [, 若存在 0 使得 [ (i≤k), 且 [, 则称序列 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
- #include<iostream>
- #include<vector>
- #include<cstdlib>
- using namespace std;
- int main(){
- int n;
- cin>> n;
- vector<int> v(n+1);
- for(int i = 1; i <= n; i++){
- cin>> v[i];
- }
- for(int i = 1; i <= n; i++)
- for(int j = i + 1; j <= n; j++){
- vector<int> lie,a(n+1,1);
- a[i] = a[j] = -1;
- for(int k = 1; k <= n; k++){
- if(v[k] * a[abs(v[k])] < 0)
- lie.push_back(k);
- }
- if(lie.size() == 2 && a[lie[0]] + a[lie[1]] == 0){
- cout << i << " " << j << endl;
- return 0;
- }
- }
- cout << "No Solution" << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2967774.html