PAT甲级1148.

目录

A1148

题目

样例

样例1

输入:

5
-2
+3
-4
+5
+4

输出:

1 4

样例2

输入:

6
+6
+3
+1
-5
-2
+4

输出:

1 5

样例3

输入:

5
-2
-3
-4
-5
-1

输出:

No Solution

思路和坑点

　　思路：
　　我们假定两个人是狼人，然后由此判定其他人的说法，如果发现刚好满足题设条件，则说明当前假设成立，否则没有满足条件的输出，则认为无解。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif 
    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);                   //记录说谎者和假定的身份（1表示好人，-1表示狼人，初始化为1）
            a[i]=a[j]=-1;                               //假定i和j都是狼人
            for(int k=1;k<=N;k++){                      //遍历每个人说的话
                if(v[k]*a[abs(v[k])]<0)                 //v表示第k个玩家说的话，与相对应的描述的另一位玩家abs[v[k]]的身份进行比对，如果符号（身份）不同，乘积小于0，即说明此人说谎
                    lie.push_back(k);                   //保存说谎玩家的序号
            }
            if(lie.size()==2&&a[lie[0]]+a[lie[1]]==0){  //如果说谎玩家刚好有两个，而且一个狼人一个好人（题目要求只有两个狼人，有狼人说谎且不是所有狼人都说谎）
                cout<<i<<' '<<j;                        //如果满足题目条件，说明当前的假设成立，也就是i和j都是狼人，输出即可
                return 0;
            }
        }
    }
    cout<<"No Solution";                                //如果没有满足条件的输出，则无解
    return 0;
}