C++ 二分答案 一本通

Question

C++ http://ybt.ssoier.cn:8088/problem_show.php?pid=1243

#include<iostream>
using namespace std;
int n,m,a[1001],num;
bool check(int n)
{
    int s=0,k=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>n)
        {
            return 0;
        }
        if(s+a[i]<n)
        {
            s+=a[i];
        }
        else
        {
            s=a[i];
            k++;
        }
    }
    if(k>=m)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
int main()
{
    int l,r,ans=0,min=1e5+9,mid;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        ans+=a[i];
        min=(min>a[i]?a[i]:min);
    }
    l=min;r=ans;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))r=mid-1;
        else {num=mid;l=mid+1;}
    }
    cout<<num;
    return 0;
}

疑问：
所有测试点均 运行错误
怎么找都找不到

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

这道题是二分答案的模板题，你的代码基本上是正确的，但是有两个小问题。

首先，你初始化变量 min 时，应该把它设成一个很大的数，而不是一个很小的数。因为后面你要找一个最小的能够满足条件的数，如果 min 被设成一个很小的数，可能会导致找到的解比实际解还要小，从而导致错误答案。

其次，你输出的是 num，但是 num 只有在 check(mid) 的结果为 false 时才被赋值，也就是说，当所有 check(mid) 的结果都为 true 时，num 的值不会被更新。因此，你应该在二分的过程中记录一个最小的满足条件的数，而不是只记录最后一次不满足条件的数。可以在二分的过程中添加一个变量 ans，表示当前找到的最小的满足条件的数，每次找到一个满足条件的数时，更新 ans，最后输出 ans 即可。

下面是修改后的代码：

#include <iostream>
using namespace std;

int n, m, a[1001];

bool check(int x) {
    int s = 0, cnt = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] > x) {
            return false;
        }
        if (s + a[i] <= x) {
            s += a[i];
        } else {
            cnt++;
            s = a[i];
        }
    }
    return cnt <= m;
}

int main() {
    int l = 1, r = 1000000000, ans = -1;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

另外，注意在二分时，应该把右边界初始化为一个比所有数的和还要大的数，因为最大的数加上其他数的和可能会超过 int 类型的范围，导致计算错误。