H - Prince and Princess 計蒜客 - 42402

題意:

你現在要尋找公主，有三種人，第一種是說真話的人(至少為1，因為公主是說真話的人)，第二種人是只會說假話的，第三種是胡說八道的(說的話真假都有可能)。現在給你三種人的數量，你對于任何一個人可以問三種問題：
1.你是誰
2.誰在指定的房間里
3.公主在哪個房間
問最少問多少問題找到公主，如果找不到輸出NO

題解：

我們可以分析出，三種問題只有第三個有用，我們要考慮極端情況下如何找到公主，極端情況就是第二，三種人會統一說一樣的錯誤的答案，所以我們要找到公主必須保證說真話的人>說假話+胡說八道的人，也就是a>b+c一定有解，最少問問題數量，極端情況下我們一開始問到的都是第二，三種人，也就是我們會得到b+c個錯誤的房間答案，然后問到的都是正確的人，當一個房間的答案>b+c后，說明這就是正確答案，因為a>b+c,所以正確答案一定大于b+c,所以最少問(b+c)+(b+c)+1
但是有個坑，如果a=1，b=0，c=0，此時一個問題也不用問，因為a=1這個人就是公主，就公主一個人還問啥問題，直接就找到了，腦筋急轉彎。。。

代碼:

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() {int a,b,c;cin>>a>>b>>c;if(a>(b+c)){puts("YES");if(a==1&&b==0&&c==0)cout<<0;else cout<<(b+c)*2+1;}else {puts("NO");}return 0; }

總結

以上是生活随笔為你收集整理的H - Prince and Princess 计蒜客 - 42402的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。