PAT 1148 Werewolf – Simple Version – 甲级

题目不再赘述,思路写在代码注释中了,借鉴了柳神的代码,但思路不是很好懂,因此添加了个人的理解
.

#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;
}
PAT 1148 Werewolf – Simple Version – 甲级PAT 1148 Werewolf – Simple Version – 甲级 浮沉随浪。 发布了19 篇原创文章 · 获赞 7 · 访问量 1万+ 私信 关注
上一篇:【随笔】【python】装饰器


下一篇:AOP的姿势之 简化 MemoryCache 使用方式