重复尝试后 AC 了,算法大概是没问题,不知道为什么会引入某种不确定性因素导致 RE 。有时甚至直接 CE 。
#include <iostream>
using namespace std;
typedef long long ll;
ll l, *stones;
int n, most;
bool canDo(ll m)
{
int removed = 0;
int before = 0;
for (int i = 0; i < n; i++)
{
if (stones[i] - before >= m)
before = stones[i];
else
removed++;
}
if (l - before < m)
removed++;
// cout << m << ':' << removed << endl;
return removed <= most;
}
int main()
{
ios::sync_with_stdio(false);
cin >> l >> n >> most;
stones = new ll[n];
for (int i = 0; i < n; i++)
cin >> stones[i];
ll left = 1;
ll right = l;
while (left < right)
{
ll mid = (left + right) / 2;
if (canDo(mid))
left = mid + 1;
else
right = mid - 1;
}
if (canDo(left))
cout << left;
else
cout << left - 1;
return 0;
}