用二分答案,为什么一改判定条件就WA了呢,跪求大佬解惑
查看原帖
用二分答案,为什么一改判定条件就WA了呢,跪求大佬解惑
429103
Archiepuls楼主2021/3/28 21:11

在判断的时候为什么判定条件是:当砍的长度小于应该砍的总长度的时候return false,但是当判定条件是砍的长度大于砍的总长度的return false的时候就WA了呢?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
ll n,m;
ll a[N];    
bool judge(ll x)
{
    ll sum=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]>x) sum+=a[i]-x;
    }
    if(sum<m) return false;
    else return true; 
}
int main()
{
    cin>>n>>m;
    if(n==1)
    {
        cin>>a[0];
        cout<<a[0]-m<<endl;
        return 0;
    } 
    for(ll i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    ll left=a[0],right=a[n-1],mid,x;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(judge(mid))
        {
            x=mid;
            left=mid+1;
        }
        else
        {
            right=mid-1;
        }
    }
    cout<<x<<endl;
    return 0;
}```
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
ll n,m;
ll a[N];    
bool judge(ll x)
{
    ll sum=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]>x) sum+=a[i]-x;
    }
    if(sum>m) return true;
    else return false; 
}
int main()
{
    cin>>n>>m;
    if(n==1)
    {
        cin>>a[0];
        cout<<a[0]-m<<endl;
        return 0;
    } 
    for(ll i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    ll left=a[0],right=a[n-1],mid,x;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(judge(mid))
        {
            left=mid+1;
        }
        else
        {
            x=mid;
            right=mid-1;
        }
    }
    cout<<x<<endl;
    return 0;
}```
2021/3/28 21:11
加载中...