PAT - [1148] Werewolf - Simple Version (20分)

进行模拟，假定两个人为狼人看是否符合条件

Vocabulary

1. ascending 升序的

自己的想法

进行模拟，假定两个人为狼人看是否符合条件
冷静可以解决一切问题！
思路没有问题，但是代码可以精简很多

自己的代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
    vector<int> in;
    for(int i=0;i<n;++i){
        int t;
        scanf("%d",&t);
        in.emplace_back(t);
    }
    int w1 = 0,w2 = 1;//假设狼人为w1和w2
    for(;;){
        bool flag = true;
        int countL = 0;
        //1.先判断两个狼人是否全说的真话，若全说的真话则为假，若全说的假话则为假
        if(in[w1]>0){
            //w1说某人是人，判断这个人是不是两个狼人之一，若是则为假话，否则为真话
            if(in[w1]==(w1+1)||in[w1]==(w2+1)) ++countL;
        }else{
            //w1说某人是狼人，如果这个人不是二者之一，则说的假话
            if((-in[w1])!=(w1+1)&&(-in[w1])!=(w2+1)) ++countL;
        }
        //判断w2
        if(in[w2]>0){
            if(in[w2]==(w1+1)||in[w2]==(w2+1)) ++countL;
        }else{
            if((-in[w2])!=(w1+1)&&(-in[w2])!=(w2+1)) ++countL;
        }

        //2.判断共有几个说谎的人，如果不为2则为假
        if(countL==0||countL==2){
            flag = false;
        }else{
            //剩下的人中必须只能有一个说谎的人
            int count = 0;
            for(int j=0;j<n;++j){
                if(j==w1||j==w2) continue;
                if(in[j]>0){
                    //这个人类说某人是人，若某人是w1或w2则为说谎
                    if(in[j]==(w1+1)||in[j]==(w2+1)) ++count;
                }else{
                    //这个人说某人是狼，若这个人不是w1且不是w2则为说谎
                    if(-in[j]!=(w1+1)&&-in[j]!=(w2+1)) ++count;
                }
                if(count>1){
                    flag = false;
                    break;
                }
            }
            if(count==0) flag = false;
        }
        if(!flag){
            if(w1==in.size()-2&&w2==in.size()-1){
                cout<<"No Solution";
                break;
            }else if(w2==in.size()-1){
                ++w1;
                w2 = w1+1;
            }else{
                ++w2;
            }
        }else{
            cout<<w1+1<<" "<<w2+1;
            break;
        }
    }
    return 0;

分析

每个人说的数字保存在v数组中，i从1～n、j从i+1～n遍历，分别假设i和j是狼人，a数组表示该人是狼人还是好人，等于1表示是好人，等于-1表示是狼人。k从1～n分别判断k所说的话是真是假，k说的话和真实情况不同（即v[k] * a[abs(v[k])] < 0）则表示k在说谎，则将k放在lie数组中；遍历完成后判断lie数组，如果说谎人数等于2并且这两个说谎的人一个是好人一个是狼人（即a[lie[0]] + a[lie[1]] == 0）表示满足题意，此时输出i和j并return，否则最后的时候输出No Solution～

代码优化

//代码链接 https://blog.csdn.net/liuchuo/article/details/82560876
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            vector<int> lie, a(n + 1, 1);
            a[i] = a[j] = -1;
            for (int k = 1; k <= n; k++)
                if (v[k] * a[abs(v[k])] < 0) lie.push_back(k);
            if (lie.size() == 2 && a[lie[0]] + a[lie[1]] == 0) {
                cout << i << " " << j;
                return 0;
            }
        }
    }
    cout << "No Solution";
    return 0;
}