愤怒的牛

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 937 字

二分最小距离后贪心放牛判定可行性

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1433
// 题意：N 个隔间位置已知，要把 C 头牛放进去，求任意两头牛之间最小距离的最大可能值。
// 思路：二分答案 + 贪心判定。
// 1. 对最小距离 d 二分，判定函数从左到右尽量早地放牛，相邻距离不小于 d 就放。
// 2. 判定成功说明 d 还能再大，失败则要调小。
// 复杂度：O(N log N) 时间 / O(N) 空间
// 易错点：必须先给隔间坐标排序，否则贪心放牛的距离判断毫无意义。
// 易错点：二分上界取坐标跨度，下界取 1（或 0），别把上界设成 1e9 之外的无效范围。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, c;
    if(!(cin >> n >> c)) return 0;
    vector<int> x(n);
    for(int i = 0; i < n; i++) cin >> x[i];
    sort(x.begin(), x.end());
    int l = 1, r = x[n - 1] - x[0], ans = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        int cnt = 1, last = x[0];
        for(int i = 1; i < n; i++){
            if(x[i] - last >= mid){
                cnt++;
                last = x[i];
            }
        }
        if(cnt >= c){
            ans = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

愤怒的牛

正文

一本通·提高篇的其它内容