算法知识点：二分，贪心

复杂度：

解题思路：

如果长度 可以满足，那么当长度小于 时也可以满足，所以我们可以二分出最大的 。

剩下的问题是如何判断给定 的情况下，能否最多拿走 块石头，使得所有相邻两块石头之间的距离不小于。

这一步可以贪心来做。从前往后扫描，并记一下上一块石头的位置。

  • 如果当前石头和上一块石头的距离小于 ，则将当前石头拿走。这里给出证明：如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。
  • 如果当前石头和上一块石头的距离大于等于，则将上一块石头更新成当前这块。

扫描结束后判断拿走的石头数量是否小于等于 。

时间复杂度分析:

总共二分 次，每次贪心的计算是 ，因此总时间复杂度是 。

C++ 代码： 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 50010;
 
int L, n, m;
int d[N];
 
bool check(int mid)
{
    int last = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] - last < mid) cnt++;
        else last = d[i];
    return cnt <= m;
}
 
int main()
{
    scanf("%d%d%d", &L, &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
    d[++n] = L;
 
    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
 
    printf("%d\n", r);
    return 0;
}



另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ