洛谷P7757 [COCI2012-2013#3] AERODROM 题解

题目传送门

一道二分题

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

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

所以需要二分优化

什么二分呢

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}

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


本博客所有文章除特别声明外,均采用 CC BY-NC 4.0 协议 ,转载请注明出处!