P5119 [USACO18DEC]Convention

URL 洛谷

题目描述

这是我们模拟赛题目……结果我就这道题满分……我还是太菜了。

有很多奶牛要坐车,但他们出来的时间不同,FJ有很多车去接,求等待时间最长的奶牛等待的时间的最小值

思路简述

看到要求时间的最大值的最小值,明显,这是一道二分答案题目,唯一需要思考的是其check函数的写法。

check函数运用贪心的思路,将奶牛上车时间进行排序,直接进行模拟,看是否可在每辆车都不超载,每个奶牛等待时间都不超标的情况下将所有奶牛接走。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,c,m,t[100005],l,r;
bool ok(ll x){
int r_n=0;
//printf("test%lld:\n",x);
ll u_c=1,c_h=1,t_n=t[0];//u_c指用掉的车辆数,c_h指这辆车已有的奶牛数,t_n指这辆车到达时间
for(r_n=1;r_n<n;r_n++){//遍历每个奶牛
if((t[r_n]-t_n)>x||c_h>=c){//如果奶牛等候时间过长或车满载了,就换下一辆车
t_n=t[r_n];//更新车的出发时间
c_h=0;
u_c++;
}
if(u_c>m){//如果车不够了,则不能满足条件
return 0;
}
c_h++;//增加车上的奶牛数
}
return 1;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&c);
for(ll i=0;i<n;i++) scanf("%lld",&t[i]);//输入
sort(t,t+n);//按时间排序
r=1e9+1;//注意二分的边界并不小
while(l<=r){//二分答案模板
ll mid=(r+l)/2;
if(ok(mid)){
r=mid-1;
}
else l=mid+1;
}
printf("%lld",l);//输出即可
return 0;
}