UVA11714 Blind Sorting 题解
题目链接
思路
一道结论题，代码实现非常简单。
把此题拆分成两个小问题。
-
在最坏的情况下，需要几次询问，才能找出最大的数。
-
在最坏的情况下，需要几次询问，才能找出次大数。
对于找出最大的数，可以模拟二分查找来解决，每次将左边界右移或右边界左移，最终得到最大数。因此在最坏的情况下，查找最大值最多需要 \(\lfloor \log_2 n -1 \rfloor\) 次。
而次大数的话，就只能老老实实的挨个询问，在最坏的情况下，就需要 \(n-1\) 次。
将两个子问题所需最多询问次数相加，即是我们需要的最坏的询问次数。
注意：
- 有多组数据，对于每次输入的 n，都应处理并输出结果。
- 使用 cmath 库内的 log2 函数时，记得向下取整。
参考代码（请勿抄袭）：
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
while(scanf("%d",&n)){
printf("%d\n",int(log2(n-1))+n-1);//对于每组数据，都应处理输出结果并换行
}
return 0;
}