共计 1305 个字符,预计需要花费 4 分钟才能阅读完成。
题目粗心:
已知 N 名玩家中有 2 人表演狼人角色,有 2 人说的不是瞎话,有狼人扯谎但并不是所有狼人都在扯谎。要求你找出表演狼人角色的是哪几号玩家,如果有解,在一行中按递增程序输入 2 个狼人的编号;如果解不惟一,则输入最小序列解;若无解则输入 No Solution.
算法思路:
题意不太好了解,此题没有考查任何算法技巧,是一个模拟题,重点在于依据给定的信息假如一个确定条件,在搜寻过程中,呈现同时合乎第二个条件的就是解,具体来说就是,题目给定了 2 个确定的条件,第一个就是有且仅有 2 个狼人,第二个就是有 2 人说谎,一个是狼人,一个是平民。题目既然要求给出狼人的编号,那么搜寻的整体空间就是所有人,因为狼人有 2 个,所以得应用双重循环搜寻所有狼人,别离应用 i 和 j 代表 2 个狼人的编号 (i<=j)。既然当初确定了狼人的编号,就阐明第一个确定条件曾经应用,当初就是须要晓得怎么晓得一个人有说谎了,其实也很简略,每次搜寻的时候,咱们给所有人一个初始状态,均为 1,示意平民,让 i 和 j 为 - 1 示意狼人,如果有一个人 k 说的话指定的那个人的状态 a[k] 与其当初自身的状态不统一就阐明 k 在说谎。具体的做法就是,应用 state 初始化为 1,state[i] = state[j] = -1;
遍历每一个人的编号,只有 a[k]*state[abs(a[k])]<0
(a[k] 为 k 所说的那个人的身份),就阐明 k 在说谎, 记录下来,增加进 liars 中,只有liars.size()==2&&state[liars[0]]+state[liars[1]]==0
,阐明当初找到一个解, 因为是从返回后搜寻失去的后果,编号肯定是最小的,间接退出循环。
考场上要是遇见这个题,心态可能得解体。
提交后果:
AC 代码:
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int N;
scanf("%d",&N);
int a[N+1];
for (int i = 1; i <= N; ++i) {scanf("%d",&a[i]);
}
// 暴力搜寻, 遍历所有的狼人,找到 2 个说谎的人,一人是平民,一人是狼人
for (int i = 1; i <= N; ++i) {for (int j = i+1; j <= N; ++j) {
// 首先初始化每一个人的状态,假如都是平民
int state[N+1];
fill(state,state+N+1,1);
//(i,j)是一对狼人
state[i] = state[j] = -1;
// 只有以后人说的话与那个人的身份不合乎,阐明在说谎
vector<int> liars;
state[i] = state[j] = -1;
for (int k = 1; k <= N; ++k) {if(a[k]*state[abs(a[k])]<0){
// k 在说谎, 记录下来
liars.push_back(k);
}
}
if(liars.size()==2&&state[liars[0]]+state[liars[1]]==0){
// 找到一组解
printf("%d %d",i,j);
return 0;
}
}
}
printf("No Solution");
return 0;
}