算法
(二分,贪心)
如果长度 Len 可以满足,那么当长度小于 Len 时也可以满足,所以我们可以二分出最大的 Len
剩下的问题是如何判断给定 Len 的情况下,能否最多拿走 M 块石头,使得所有相邻两块石头之间的距离不小于 Len
这一步可以贪心来做。从前往后扫描,并记一下上一块石头的位置。
如果当前石头和上一块石头的距离小于 Len,则将当前石头拿走。这里给出证明:如果某个最优解中是拿走了上一块石头,那么我们可以改成留下上一块石头,拿走当前这块石头,这样总共拿走的石头数量不变,所以当前选法也是一组最优解。
如果当前石头和上一块石头的距离大于等于 Len,则将上一块石头更新成当前这块。
扫描结束后判断拿走的石头数量是否小于等于 M。
#include <bits/stdc++.h>
#define N 50001
using namespace std;
int n, m, l, d[N];
bool check(int len)
{
int cnt = 0, last = 0;
for(int i = 1; i <= n; ++ i)
if(d[i] - last < len) cnt ++;
else last = d[i];
return cnt <= m;
}
int main()
{
cin >> l >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> 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;
}
cout << r << endl;
return 0;
}