问题标题: 洛谷：P1873 砍树二分炸

Question

0

已解决

黄子扬

初级天翼

#include<bits/stdc++.h>
using namespace std;
long long a[1000005],n,m,tot;
bool P(int h)
{
    for(int i=1;i<=n;i++)
        if(a[i]>h)
            tot+=a[i]-h;
    return tot>=m;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int L=0,R=1e9,ans,mid;
    while(L<=R)
    {
        if(P(mid=L+R>>1))
            ans=mid,L=mid+1;
        else
            R=mid-1;
     } 
    printf("%d",ans);
    return 0;
}

样例输出57

Answer 1

已采纳

王子健

初级天翼

然而这题并不需要什么二分法。。。

用sort排序再从后往前查找就可以。

只需优化一下当前砍去多少米的算法就可以。

假设已砍过了i棵树（树由高到低排），那此时被砍过的i棵树的高度均等于第i+1棵树的高度。

再砍一棵树（砍第i+1棵）后获得的新高度为（第i+1棵树的高度-第i+2棵树的高度）*（i+1）。

so 时间复杂度仅为 n

(摘自洛谷题解，仅供参考)

问题标题: 洛谷：P1873 砍树 二分炸

1 个回答:

问题标题: 洛谷：P1873 砍树二分炸