错误代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e6 + 10;
long long a[N];
long long l = 0, r = -1;
long long sum;
int main()
{
    long long n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        r = max(r, a[i]);
    }

    while (l < r)
    {
        long long mid = l + r >> 1;

        sum = 0;
        for (int i = 0; i < n; i++)
            if (a[i] > mid)
                sum += a[i] - mid;

        if (sum <= m) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

AC代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e6 + 10;
long long a[N];
long long l = 0,r = -1;
long long sum;
int main()
{
    long long n,m;
    cin>>n>>m;
    
    for(int i = 0;i < n;i ++)
    {
        cin>>a[i];
        r = max(r,a[i]);
    }
    
    while(l < r)
    {
        long long mid = l + r >> 1;
        
        sum = 0;
        for(int i = 0;i < n;i ++)
            if(a[i] > mid) 
                sum += a[i] - mid;
            
        if(sum < m) r = mid;
        else l = mid + 1;
    }
    cout<<l - 1;
    return 0;
}

假设数据为：

• 9 20
• 1 2 3 4 5 6 7 8 9

1. l = 0,r = 9,mid = 4,sum = 15
2. l = 0,r = 4,mid = 2,sum = 28
3. l = 3,r = 4,mid = 3,sum = 21

• 易知，sum存在无法等于m的情况，因此二分时无法得到正好sum等于m的答案。
• 因此，在有答案的前提下，应该一开始就寻找正确答案旁边的情况，并进行修正。