起因是看到高赞题解后对judge函数的终止条件感到疑惑,然后自己分析了一下更改了循环终止条件发现仍然能AC,就自己构造了一个数据
下面是错误的AC代码
#include <iostream>
using namespace std;
int l, n, m;
int *stones;
// 判断这个解是否满足题意
bool judge(int x)
{
int count = 0;
int i = 1;
int now = 0;
while (i <= n)
{
if (stones[i] - stones[now] < x) // 两石头的间隔小了,需要撤石头
++count;
else // 满足间隔就跳
now = i;
++i;
}
return count <= m;
}
int main()
{
cin >> l >> n >> m;
stones = new int[n + 2];
stones[0] = 0; // 起点
for (int i = 1; i <= n; i++)
{
cin >> stones[i];
}
stones[n + 1] = l; // 终点
int b = 1, e = l; // 设置左右边界
int ans = 0;
while (b <= e)
{
int m = (b + e) / 2;
if (judge(m)) // 如果满足题意,记录下当前答案,左端点右移看看有没有更优解
{
ans = m;
b = m + 1;
}
else // 不满足题意,右端点左移排除错误区间
{
e = m - 1;
}
}
cout << ans << endl;
return 0;
}
这是自己构造的数据
8 3 1
2
4
7
正确答案应该为2,但是错误AC代码跑出来的结果是3
希望有大佬能帮我看看这个数据是不是HACK数据
如果我想错了的话请指正