思路：二分

随着种树区间的增长，公路上被种上的树的数量单调不降，具有单调性，因此可以使用二分解决。

二分种树区间长度，并$O(N)$扫一遍工人的种树区间，判断能否种上$k$棵树，能就减少二分长度，否则增大二分长度。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> arr;

bool check(int s) {
    int la = -1, cnt = 0;
    for(int i = 0 ; i < n ; i ++) {
        int x = max(la, arr[i]), y = arr[i] + s - 1;
        cnt += y - x + 1;
        la = y + 1;
    }
    return cnt >= k;
}

int main()
{
	std::ios::sync_with_stdio(false);
    cin >> n >> k;
    arr.resize(n);
    for(int i=0;i<n;++i){
    	cin>>arr[i];
	}
	sort(arr.begin(), arr.end());
	int l = 1, r = k;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout<<r+1;
}

题目内容

​ 长度无限长的公路上，小美雇佣了$n$位工人来种树，每个点最多种一棵树。

从左向右数，工人所站的位置为$a_1,a_2,...,a_n$。已知每位工人都会将自己所在位置的右侧一段长度的区间种满树，且每位工人的种树区间长度相同。

现在小美希望公路上至少有$k$棵树，为了节约成本，他希望每位工人种树的区间长度尽可能短，请你帮他求出，工人们的种树区间至少多长，从能使得公路被种上至少$k$棵树。

输入描述

第一行输入两个正整数$n$，$k$($1≤n,k≤2×10^5$),分别为表示工人的数量，以及小美要求树的最少数量。

第二行输入$n$个正整数$a_1,a_2,...,a_n$($1≤a_i≤2×10^5$),表示每名工人的位置。

输出描述

在一行输出一个整数，代表工人们最短的种树区间长度。

样例1

输入

3 6
1 2 5

输出

3

说明

每位工人种树的区间长度至少为$3$。

这样以来：

第一名工人种：$1,2,3$点的树。

第二名工人种：$2,3,4$点的树。

第三名工人种：$5,6,7$点的树。

由于每个位置最多种一棵树，因此共有：$1,2,3,4,5,6,7$这些点有树，满足至少$k=6$棵树