P4779 团队猜数（基础）

三个人组队玩猜数游戏，每人猜一个不超过 10 亿的正整数，三个人都学会了二分法猜数。题目要求统计三个人猜数的总次数。

解题思路

1. 每个人的猜法一样。 都在 1 到 10 亿的范围内用二分法猜：low = 1，high = 1000000000，每次猜中间值 mid = (low + high) / 2。

2. 写一个函数统计次数。 countTimes(要猜的数) 在 1 到 10 亿范围内二分，每猜一次计数加 1，直到 mid 等于要猜的数就返回次数。如果 mid 比答案大就往左半边猜（high = mid - 1），比答案小就往右半边猜（low = mid + 1）。

3. 把三个人加起来。 分别算出三个数需要的次数，再相加就是团队总次数。

4. 具体例子。 三个数是 1000000、5000000、100。猜 1000000 需要 29 次，猜 5000000 需要 27 次，猜 100 需要 28 次，总次数 29 + 27 + 28 = 84，输出 84。

5. 边界情况。 如果三个人都猜同一个数，比如都猜 1，每个人都要 29 次，总共 87 次；数字不同，每个人的次数也略有不同，但都在 30 次以内。

参考代码

// 团队猜数：统计三人各用二分法在1到10亿范围内猜数所需次数之和
#include <iostream>
using namespace std;
// 在1到10亿范围内用二分法猜中target需要的次数
int times(int target){
    int low = 1, high = 1000000000;
    int cnt = 0;
    while(low <= high){
        cnt++;
        int mid = (low + high) / 2; // 中间值
        if(mid == target){
            break; // 猜中了
        } else if(mid > target){
            high = mid - 1; // 数字太大，往左半边猜
        } else {
            low = mid + 1;  // 数字太小，往右半边猜
        }
    }
    return cnt;
}
int main(){
    int num1, num2, num3;
    cin >> num1 >> num2 >> num3;
    int total = times(num1) + times(num2) + times(num3);
    cout << total << endl;
    return 0;
}

复杂度分析

范围是 1 到 10 亿，二分法每次减半，猜一个人的数最多约 30 次，时间复杂度是 O(log 10^9)，也就是常数级别。三个人就调用三次函数，总共还是常数时间。程序只用了几个变量，空间复杂度是 O(1)。