洛谷P7757题解
#题解 2025-02-04

一道二分题

如果使用贪心，则会有时间复杂度

因为数据范围 且 所以在最坏情况下会 TLE

所以需要二分优化

什么二分呢

二分法分为二分查找与二分答案，二分查找注重于在一个集合（有序）里找到一个数，而二分答案注重于找到答案，简单来说，就是假设答案再判断对错，做调整

不难写出二分模版

1
2
3
4
5
while(l < r){
    mid = (l + r) >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
}

这样一来 的复杂度就降到了

我们只需要根据题意改改模版即可

此题思路：我们需要计算出每个服务台可办理的人数之和，然后判断是否大于，小于所给人数，进行二分法即可

AC Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
long long n, m, t[100005], ans, l = 1, r;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        if(t[i] >= r) r = t[i]; //找到集合t中的最大值
    }
    r *= m;//人数*服务台的最大时间，得最坏情况
    long long cnt, mid;
    while(l < r){//此处也可以用一个函数去写
        mid = (l + r) >> 1, cnt = 0; //此处mid为l+r的一半
        //并初始化cnt（用来计数人数之和）为0
        //(x>>1)=(x/2)
        for(int i = 1; i <= n; i++) cnt = cnt + mid / t[i]; //计算出每个服务台能办理的人数之和
        if(cnt >= m) r = mid; //人数之和超过了总人数,使二分范围的最右边变成当前中间值
        else l = mid + 1;//人数之和不到总人数,使二分范围的最左边变成当前中间值+1（中间值已经判断过）
    }
    //二分完的结果是l=r，即最终答案，因此输出l或者r都可以
    cout << r << endl;
    return 0;
}

有哪里说的不对或者不是很好的请提出！谢谢各位！