Description
狼人杀游戏,第几个人说第几个人是狼人或者是人,规定所有人中有两个狼人,其中只有一个狼人和一个人说谎,要求找出两个狼人
Input
第一行n,代表n个人
接下来n行
正数 Di 代表:第i个人说第Di人是human
负数 Di 代表:第i个人说第Di(绝对值)人是werewolf
Output
输出两个werewolf的下标,一个空格,如果有多个答案,输出最小的序列
解题思路
算法标签:枚举
显然就是枚举任意两个人是狼人,统计n个人说谎的人数,如果说话人数为两人,且一个为狼人另一个为人,当然没有规定这两个人谁是狼人谁是人,只是要求其中一个是狼人,另一个是人就行,遍历从小到大遍历,第一个找到的自然是最小的,无任何算法,不需要任何技巧,简单遍历即可(没玩过狼人杀但是可以百度啊!没吃过猪肉还没见过猪跑嘛)
代码
//freopen("hao.txt","r",stdin);
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int N = 105;
int main()
{
int n = 0;
int statement[N] = {0};
bool isans = false;
// ture为human,false为werewolf
bool iswolf[N];
cin>>n;
for(int i=1;i<=n;i++)
cin>>statement[i];
for(int i=1;i<n;i++) {
for(int j=i+1;j<=n;j++) {
// 初始化均为human
memset(iswolf,true,sizeof(iswolf));
// 创建说谎人的队列,存储下标
queue<int>liar;
//cout<<i<<" "<<j<<endl;
// 认为第i个人和第j个人是狼人,这样就可以保证答案从小到大
iswolf[i] = false;
iswolf[j] = false;
// 寻找有几个人是说谎的,以及说谎人是不是一个werewolf和human
for(int k=1;k<=n;k++) {
if((statement[k]>0)&&(iswolf[abs(statement[k])]==false))
liar.push(k);
else if((statement[k]<0)&&(iswolf[abs(statement[k])]==true))
liar.push(k);
}
if(liar.size()==2) {
int liar_a = liar.front();
int liar_b = liar.back();
if(iswolf[liar_a]==true && iswolf[liar_b]==false) {
cout<<i<<" "<<j;
isans = true;
break;
}
else if(iswolf[liar_a]==false && iswolf[liar_b]==true) {
cout<<i<<" "<<j;
isans = true;
break;
}
}
}
if(isans)
break;
}
// 判断是否有答案
if(!isans)
cout<<"No Solution";
return 0;
}