P7757题解

hopeless_hope · 2021-10-10 16:48:23 · 题解

一道二分题

如果使用贪心，则会有时间复杂度 O(m \log_{} {n})

因为数据范围 m \le 10^9 且 n \le 10^5 所以在最坏情况下会 TLE

所以需要二分优化

什么二分呢

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

这里借用一张动图来方便大家来理解二分查找：

根据动图，不难写出二分查找/答案的模版

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

这样一来 O(x)的复杂度就降到了O( log\ x)

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

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

AC Code：

#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=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;
}

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