Codeforces GoodBye 2019题解
Problem D
【题目大意】交互题,服务器那边有n个互不相同的整数,你可以提n个问题,每个问题可以包含k个位置,服务器会返回这k个数中第m大的数,让你猜出m的大小。$m<=k<n<=500$
【解题思路】
首先所有的数都是两两不相同的,并且我们一次只能问出k个数中第m大的数,所以我们每次只需要针对前k+1个数提问k+1次就可以了,这样可以减少不确定性。每次更换一个元素才能分析出对应的情况,信息集中化。
通过举几个例子分析,我们发现这样提问之后我们只能得到两种情况:
A. 返回的是这k+1个数中第m大的数,这说明去除的是一个大于m的数。
B. 返回的是这k+1个数中第m+1大的数,这说明去除的是一个小于等于m的数。
所以我们只需要统计k+1个返回结果中比较大的那个元素个数就是m的大小
1 | n = 5; k = 4; m = 3; |
【代码】
1 |
|