立志用最少的代碼做最高效的表達(dá)

---

PAT乙級最優(yōu)題解——>傳送門

---

以下文字摘自《靈機一動·好玩的數(shù)學(xué)》：“狼人殺”游戲分為狼人、好人兩大陣營。在一局“狼人殺”游戲中，1 號玩家說：“2 號是狼人”，2 號玩家說：“3 號是好人”，3 號玩家說：“4 號是狼人”，4 號玩家說：“5 號是好人”，5 號玩家說：“4 號是好人”。已知這 5 名玩家中有 2 人扮演狼人角色，有 2 人說的不是實話，有狼人撒謊但并不是所有狼人都在撒謊。扮演狼人角色的是哪兩號玩家？

本題是這個問題的升級版：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人說的不是實話，有狼人撒謊但并不是所有狼人都在撒謊。要求你找出扮演狼人角色的是哪幾號玩家？

輸入格式：
輸入在第一行中給出一個正整數(shù) N（5≤N≤100）。隨后 N 行，第 i 行給出第 i 號玩家說的話（1≤i≤N），即一個玩家編號，用正號表示好人，負(fù)號表示狼人。

輸出格式：
如果有解，在一行中按遞增順序輸出 2 個狼人的編號，其間以空格分隔，行首尾不得有多余空格。如果解不唯一，則輸出最小序列解 —— 即對于兩個序列 A=a[1],…,a[M] 和 B=b[1],…,b[M]，若存在 0≤k<M 使得 a[i]=b[i] （i≤k），且 a[k+1]<b[k+1]，則稱序列 A 小于序列 B。若無解則輸出 No Solution。

輸入樣例 1：
5
-2
+3
-4
+5
+4
輸出樣例 1：
1 4

輸入樣例 2：
6
+6
+3
+1
-5
-2
+4
輸出樣例 2（解不唯一）：
1 5

輸入樣例 3：
5
-2
-3
-4
-5
-1
輸出樣例 3：
No Solution

---

解析

由于只有兩位狼人， 并且人數(shù)不超過100， 因此，即使是3重循環(huán)，最壞情況下也只有100w的規(guī)模， 200ms完全可以承受。 因此，選擇用暴力法解決

枚舉兩個狼人， 在判斷是否說謊時，說謊的條件有兩種：
1、如果判斷到狼人，并且>0
2、如果判斷到好人，并且<0
不妨使用異或判定。 異或為真的條件是：一個條件為真，一個條件為假。 同真或同假都會輸出flase

---

#include<bits/stdc++.h> using namespace std; int main() {int N, A[105]; //數(shù)組A存儲每個玩家的說法scanf("%d", &N);for(int i = 1; i <= N; i++) scanf("%d", &A[i]);for(int i = 1; i <= N; ++i) for(int j = i+1; j <= N; ++j) {int lier = 0, wolfLier = 0; //lier是說謊玩家個數(shù)，wolfLier是說謊狼人個數(shù)for(int k = 1; k <= N; ++k) {if((abs(A[k])==i || abs(A[k])==j)^(A[k] < 0)) { //滿足表達(dá)式為說謊 ++lier; //遞增說謊玩家人數(shù)if(k == i || k == j) //說謊的玩家是狼++wolfLier; //遞增說謊的狼人個數(shù) }} if(lier == 2 && wolfLier == 1) {printf("%d %d\n", i, j); goto loop;} }puts("No Solution");loop : ;return 0; }

---

耗時

總結(jié)

以上是生活随笔為你收集整理的【简便解法】1089 狼人杀-简单版 (20分)_25行代码AC的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。