题解 | 接机-牛客假日团队赛1I题

题目描述

一场别开生面的牛吃草大会就要在Farmer John的农场举办了！

世界各地的奶牛将会到达当地的机场，前来参会并且吃草。具体地说，有头奶牛到达了机场（），其中奶牛在时间（）到达。Farmer John安排了（）辆大巴来机场接这些奶牛。每辆大巴可以乘坐头奶牛（）。Farmer John正在机场等待奶牛们到来，并且准备安排到达的奶牛们乘坐大巴。当最后一头乘坐某辆大巴的奶牛到达的时候，这辆大巴就可以发车了。Farmer John想要做一个优秀的主办者，所以并不想让奶牛们在机场等待过长的时间。如果Farmer John合理地协调这些大巴，等待时间最长的奶牛等待的时间的最小值是多少？一头奶牛的等待时间等于她的到达时间与她乘坐的大巴的发车时间之差。

输入保证。

输入的第一行包含三个空格分隔的整数，和。第二行包含个空格分隔的整数，表示每头奶牛到达的时间。

输出一行，包含所有到达的奶牛中的最大等待时间的最小值。

示例1

6 3 2
1 1 10 14 4 3

4

如果两头时间1到达的奶牛乘坐一辆巴士，时间2和时间4到达的奶牛乘坐乘坐第二辆，时间10和时间14到达的奶牛乘坐第三辆，那么等待时间最长的奶牛等待了4个单位时间（时间10到达的奶牛从时间10等到了时间14）。

解答

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++) 
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f)) 
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x); 
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x); 
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long 
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K;
LL t[maxn];
bool check(LL x){
    LL e = t[1] + x;
    int ans = 1;
    int num = K;
    for(int i = 1; i <= N; i ++){
        if(t[i] <= e && num){
            num--;
        }else{
            e = t[i] + x;
            num = K - 1;
            ans++;
        }
    }
    return ans <= M;
}
LL solve(){
    LL l = 0,r = INF;
    LL ans = INF;
    while(l <= r){
        LL m = l + r >> 1;
        if(check(m)){
            r = m - 1;
            ans = m;
        }else{
            l = m + 1;
        }
    }
    return ans;
}
int main(){
    Sca3(N,M,K);
    for(int i = 1; i <= N; i ++) Scl(t[i]);
    sort(t + 1,t + 1 + N);
    Prl(solve());
    return 0;
}