H - Prince and Princess 计蒜客 - 42402

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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。