P1873 [COCI 2011/2012 #5] EKO / 砍树

· · 题解

P1873 [COCI 2011/2012 #5] EKO / 砍树

P1873 [COCI 2011/2012 #5] EKO / 砍树

题意分析：已知树木的数量n，需要的木材总长度M，每棵树的高度a[n]，需要求锯片的最高高度。原理就是我要找到一个锯片高度ans，每棵树比锯片高度高的部分就是我们得到的木材，比ans矮的部分不会被砍掉。解题步骤如下：

第一步：先读入相关数据；

第二步：自定义函数来判断当锯片的高度为x时，我得到的木材是否满足需要；

第三步：利用二分法来一步步查找锯片高度满足条件的情况下的最大值；锯片高度最小值是0代表所有树砍光，最大值是10的9次方（题中说明树的高度的取值范围）；

第四步：输出最后的答案ans就是我们最后找到的能满足需要的锯片最大高度值。

//P1873 [COCI 2011/2012 #5] EKO / 砍树
#include <iostream>
#include <algorithm>
using namespace std;
int ans,n,m,a[1000003];//ans表示锯片最高的高度 

bool find(int x){//判断锯片高度x能不能得到需要的木材长度 
    long long sum=0;//砍树得到的木材长度
    for (int i=0;i<n;i++){//循环遍历N棵树 
        if ((a[i]-x)>0){//如果树的高度被砍掉mid还大于0表示可以得到木材 
            sum+=a[i]-x;//把砍下来的木材累计入得到的木材总长度 
            if (sum>=m) return 1;//如果现在得到的木材已经达到了需要的木材长度m，就直接返回满足条件1 
        }
    } 
    if (sum>=m) return 1;//如果得到的木材达到了需求就满足条件 
    else return 0;//否则不满足条件 
}
int main(){
    cin>>n>>m;// N 表示树木的数量，M 表示需要的木材总长度
    for (int i=0;i<n;i++) cin>>a[i];//读入每棵树的高度 
    //因为需要木材长度为m，那么就可以查找1~m之间砍掉的高度满不满足要求
    int l=1,r=1e9;//定义左右端点,锯片的高度最少是1，最多是10的9次方 
    while (l<=r){
        int mid=l+(r-l)/2;//这样是为了防止(l+r)溢出int范围
        if (find(mid)){//如果mid能满足条件得到相应木材，那就继续往右边大的部分找 
            ans=mid;//因为当前mid能得到需要的木材，先记录为答案，后续有更大的值再更新 
            l=mid+1;//继续找右半部分，把左端点更新到后面 
        } 
        else{//否则mid不满足条件，那就肯定往左侧的部分找,右端点左移 
            r=mid-1;
        } 
    } 
    cout<<ans<<endl;//输出最后的ans，一定是所能满足条件的锯片最高高度 
    return 0;
}