PAT 乙级 1089 狼人杀-简单版

• • 1. 题目简述及在线测试位置
  • 2. 基本思路
  • 3. 完整AC代码

1. 题目简述及在线测试位置

1.1 N个人玩狼人杀，每个人 按从1到N的编号 顺序说明他人的身份，已知 N个人里面有两个狼人、有两个人在描述他人身份时说了谎话、只有一个狼人说了谎话，根据上述信息判断出谁是狼人
1.2 在线测试位置： 1089 狼人杀-简单版

2. 基本思路

2.0 想破头系列：一开始按求解数学题的思路去编码：第一个人可能有四种状态（人说真话、人说假话、狼说真话、狼说假话），按设定的状态逐步进行推导，发现根本编不下去啊… 最后发现正确的姿势应该是： 类似解方程（找到规律/方程式），用所有已知条件去尝试（计算机擅长啊），找到满足规律/方程式的条件
2.1 最终的结果需要满足 身份描述（其中两个人说了谎话，这两个人中一个是狼人），将身份描述信息存储到整型数组中。例如，PeopleWord[1]=6 第一个玩家说第六个玩家是人；PeopleWord[3]=-4 第三个玩家说第四个玩家扮演狼人

	for (int i = 1; i <= N; i++)
	{
		cin >> Data;
		PeopleWord[i] = Data; 
	}

2.2 通过计算机可以遍历所有可能的狼人组合：-1 -2，-1 -3 ，-1 -4 等等，狼人身份确定，每个人的身份状态也就随之确定了

	for (i = 1; i < N; i++)
	{
		for (j = i + 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
				Status[i] = 1;
			Status[i] = Status[j] = -1;
		}
	}		

2.3 将每个人的身份状态 与 身份描述信息 进行比对：当身份描述信息 和 身份状态不一致时，说明身份状态对应的述说者在说谎

CountLiar = 0;
for (int k = 1; k <= N; k++)
{
	int tmp = PeopleWord[k];//the k said

	if ( Status[Abs(tmp)] * tmp < 0 ) //standard for tell lies
		Liar[CountLiar++] = k; //k tell lies
}

2.4 当满足 说谎人数是2人 且 仅其中一人扮演狼人时，说明每个人的身份状态都是正确的，即找到了答案

if (CountLiar == 2 )
{
		if ((Liar[0] == i || Liar[0] == j) && (Liar[1] != i && Liar[1] != j))
		{
			cout << i << " " << j << endl;
			return 0;
		}					
		else if ((Liar[1] == i || Liar[1] == j) && (Liar[0] != i && Liar[0] != j))
		{
			cout << i << " " << j << endl;
			return 0;
		}
	}		

2.5 由于是从小到大遍历的，因此找到的第一个满足条件的结果就是题目所要求的最小序列

3. 完整AC代码

#include <iostream>
using namespace std;

#define MAX 101

int Abs(int n);

int main()
{
	int PeopleWord[MAX]; //存储每个人的描述
	int N,Data;

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> Data;
		PeopleWord[i] = Data;
	}
	
	short Status[MAX]; //存储身份状态的数组
	short Liar[MAX],CountLiar ; //统计说谎者  Liar数组计数器
		
	int i, j;
	for (i = 1; i < N; i++)
	{
		for (j = i + 1; j <= N; j++) //通过两层循环，遍历所有可能的狼人组合
		{
			//初始化
			for (int i = 1; i <= N; i++)
				Status[i] = 1;
			CountLiar = 0;
			Status[i] = Status[j] = -1; //狼人

			for (int k = 1; k <= N; k++)
			{
				int tmp = PeopleWord[k];//the k said
	
				if ( Status[Abs(tmp)] * tmp < 0 ) //standard for tell lies
					Liar[CountLiar++] = k; //k tell lies
			}

			if (CountLiar == 2 )
			{
				if ((Liar[0] == i || Liar[0] == j) && (Liar[1] != i && Liar[1] != j))
				{
					cout << i << " " << j << endl;
					return 0;
				}					
				else if ((Liar[1] == i || Liar[1] == j) && (Liar[0] != i && Liar[0] != j))
				{
					cout << i << " " << j << endl;
					return 0;
				}
			}			
		}
	}

	cout << "No Solution";

	return 0;
}

int Abs(int n)
{
	if (n < 0)
		return n * -1;
	else
		return n;
}