洛谷上的一道砍树问题

lsmCC

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e6+10;
int a[N];
void putin()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
}
int check(int k)
{
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(k>a[i])sum+=k-a[i];
        else sum+=0;
    }
    return sum;


}

int cut()
{
    int l=1,r=1e9;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid)>m)l=mid+1;//取多了，将H提高，保证是那个值
        else if(check(mid)<m)r=mid-1;
        else
        {
        return mid;
        return 0;
        }
        
    }
    return r;
    
}
int main()
{
    putin();
    cout<<cut()<<endl;

}

我的cut()里面的代码不对，应该怎么修改呢

isdkz

你需要在cut()函数中做一些修改。在当前的代码中，你在while循环中使用二分查找来寻找满足条件的最小值。但是在找到满足条件的值后，你直接返回了该值，而没有考虑到可能存在多个满足条件的值。

你需要修改cut()函数中的代码，使得它可以找到满足条件的最小值，并返回该值。你可以使用一个变量来记录满足条件的最小值，然后在循环结束后返回这个最小值。

以下是修改后的cut()函数的代码：

int cut()
{
    int l=1,r=1e9;
    int result = -1; // 用来记录满足条件的最小值
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid)>m)
            l=mid+1;
        else if(check(mid)<m)
            r=mid-1;
        else
        {
            result = mid; // 找到一个满足条件的值
            r = mid - 1; // 继续向左搜索，找到更小的满足条件的值
        }
    }
    return result;
}

通过这样的修改，cut()函数将能够正确地找到满足条件的最小值，并返回该值。