URL 洛谷

题目描述

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

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

思路简述

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

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

代码

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