题解 P5119 【[USACO18DEC]Convention S】

WRuperD · 2020-10-01 12:01:57 · 题解

更好的阅读体验

1.题意：

有n头奶牛在不同时间到达了机场，你有m辆车，每车做c头奶牛，问所有到达的奶牛中的等待时间最长的那只至少等待多少时间。

2.1 用什么算法？

首先，暴力枚举明显不行，但又没有其他较为高深的算法，所以考虑效率较高的二分答案。

2.2 怎么用？

二分的原理再次不多阐述，这里只用二分每头牛的最大等待时间，如果所有牛都可以在这个时间内（<=）等到车，r = mid - 1， 否则l = mid + 1。

3.1 代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
int n, m, c;//如题,不解释 
long long a[100000 + 10];//a数组记录每只奶牛到达时间 
int check(int x) //二分基操 
{
    int num = 1;//目前用车数量 
    int cnt = 0;//目前车上牛 
    int temp = a[1]; //记录目前等待目前仍在等的最早来的奶牛的到达时间 
    for (int i = 1; i <= n; i++)
    {
        if (a[i] - temp > x or cnt == c)//满牛车走或牛等待时间超限 
        {
            num++;//车数++ 
            cnt = 1;//更新目前车上牛数 
            temp = a[i];//更新目前等待目前仍在等的最早来的奶牛的到达时间 
        } 
        else
        {
            cnt++;//车上牛数++ 
        }
    }//判断要用车数最小值是否小于FJ有的车 
    if (num <= m)
    {
        return 1;//满足条件, r = mid - 1;
    }
    else
    {
        return 0;//不满足, l = mid + 1;
    }
}
int main()
{
    cin >> n >> m >> c;
    long long l = 0, r;//二分基操 
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];//输入 
    }
    sort(a + 1, a + n + 1);//为二分保证单调不减排序 
    r = a[n] - a[1];//显然最长等到时间=最晚来的-最早来的 
    while (r >= l)//二分基操 
    {
        int mid = (l + r) / 2, q = check(mid);
        if (q)//以下上面解释过 
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << endl;//完美输出结束!!! 
    return 0;
}

4.1 总结

这是一道十分好的二分题目，但完全没到蓝题难度，顶多黄。