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

解题思路

二分锯片高度。检查某高度时，累加所有 max(0,tree-H)。得到木材不少于 $M$ 表示高度可行，可继续升高；否则降低。

复杂度分析

时间复杂度 $O(N\log H_{max})$，空间复杂度 $O(N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;long long m;cin>>n>>m;vector<int>a(n);int hi=0;for(int&i:a){cin>>i;hi=max(hi,i);}int lo=0,ans=0;
    while(lo<=hi){int mid=lo+(hi-lo)/2;long long got=0;for(int x:a)if(x>mid)got+=x-mid;if(got>=m)ans=mid,lo=mid+1;else hi=mid-1;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;long long m;cin>>n>>m;vectora(n);int hi=0;for(int&i:a){cin>>i;hi=max(hi,i);}int lo=0,ans=0; while(lo<=hi){int mid=lo+(hi-lo)/2;long long got=0;for(int x:a)if(x>mid)got+=x-mid;if(got>=m)ans=mid,lo=mid+1;else hi=mid-1;} cout<<ans<<'\n';return 0; }