P1873 砍树 题解

凌夜绝夕 · 2020-05-05 15:07:51 · 个人记录

简单的二分，但是注意，要用long long！！！

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1000010;
long long h[N];
long long n,len;
long long m;
bool check(long long x)
{
    long long sumh=0;
    for(int i=1;i<=n;i++)
        if(h[i]>x)
            sumh+=h[i]-x;
    return sumh>=len;
}
int main()
{
    scanf("%lld%lld",&n,&len);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
        m=max(m,h[i]);
    }
    long long l=0,r=m;
    while(l<r)
    {
        long long mid=(l+r+1)/2;
        if(check(mid))   l=mid;
        else    r=mid-1;
    }
    printf("%lld\n",r);
    return 0;
}