题目不再赘述,思路写在代码注释中了,借鉴了柳神的代码,但思路不是很好懂,因此添加了个人的理解
.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> say(n + 1);
for(int i = 1; i <= n; i++)
scanf("%d",&say[i]); //第i个人的说话
/*总体思想就是用双层for循环两两判定,因为只有两个狼人,就借助设定两个狼人身份来进行双层循环寻找*/
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
vector<int> lie; //lie为最终的撒谎成员数组
vector<int> status(n + 1,1); // status为身份数组初始为 1(好人) -1(狼人)
status[i] = status[j] = -1; //设定第i 和 j 两个人为狼人,身份改为-1
/*下面的for循环为核心内容,在设定了第 i j 两人为狼人的情况下重新遍历say数组和status数组
如果在遍历结束时刚好抓住两个说谎的*/
for(int t = 1; t <= n; t++)
if(say[t] * status[abs(say[t])] < 0) //t说谎了,编号入lie
lie.push_back(t);
if(lie.size() == 2 && status[lie[0]] + status[lie[1]] == 0)
{
cout<<i<<" "<<j;//满足条件,说明i 和 j的身份设定正确,由此可以得出两个说谎的人,即一个好人和一个狼人
return 0;
}
}
}
cout<<"No Solution";
return 0;
}
浮沉随浪。
发布了19 篇原创文章 · 获赞 7 · 访问量 1万+
私信
关注