PAT 真题 | 1148 Werewolf - Simple version

这道题既然要我们找出两个狼人。那么最直达中心的求解法就是设i和j为狼人，使用二重循环遍历。 如果根据假设能推出恰好有两个说谎者（liars），那么说明满足条件，i和j就是要找的狼人。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 102;
int say[maxn];

int main()
{
    int N;
    scanf("%d", &N);
    for(int i=1;i<=N;++i){
        scanf("%d", say+i);
    }
    for(int i=1;i<=N;++i){
        for(int j=i+1;j<=N;++j){ // suppose i,j are wolvies
            vector<int> liar;
            int flag[maxn];
            fill(flag, flag+maxn, 1);
            flag[i] = flag[j] = -1;
            for(int k=1;k<=N;++k){
                int wolf = abs(say[k]);
                if (say[k] * flag[wolf] < 0){ // if k is liar
                    liar.push_back(k);
                }
            }
            if (liar.size()==2 && flag[liar[0]]+flag[liar[1]]==0){
                printf("%d %d\n", i, j);
                return 0;
            }
        }
    }
    puts("No Solution");
    return 0;
}

PS: 不敢再用C语言的 <math.h> 头文件了. 因为我使用 abs 函数的时候提示 error: ‘abs’ was not declared in this scope. 而我再Linux 下的 /usr/include/math.h 头文件下搜索 abs 的时候，发现真的没有这个函数！于是改用 <cmath> 或者 <algorithm> 了。从此写算法题对于c语言的头文件都不用 .h 写法了。