是不是hack掉了?
查看原帖
是不是hack掉了?
694710
IDEALPYJ楼主2022/8/13 11:36

起因是看到高赞题解后对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数据
如果我想错了的话请指正

2022/8/13 11:36
加载中...