1388 砍树
二分
1 #include<cstdio> 2 using namespace std; 3 #define maxx(a,b) (a>b?a:b) 4 #define minn(a,b) (a>b?b:a) 5 #define LL long long 6 LL n,m,h[1000000+15]; 7 inline void read(LL &now) 8 { 9 char ch=getchar(); now=0; 10 while(ch>'9'||ch<'0') ch=getchar(); 11 while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar(); 12 } 13 14 bool check(LL x) 15 { 16 LL t=0,tot=0; 17 for(int i=1;i<=n;i++) 18 if(h[i]>x) tot+=h[i]-x; 19 if(tot>=m) return true; 20 return false; 21 } 22 23 int main() 24 { 25 read(n); read(m); 26 LL l=0,r=0; 27 for(int i=1;i<=n;i++) 28 { 29 read(h[i]); 30 r=maxx(r,h[i]); 31 l=minn(l,h[i]); 32 } 33 while(l+1<r) 34 { 35 LL mid=(l+r)>>1; 36 if(check(mid)) l=mid+1; 37 else r=mid-1; 38 } 39 printf("%lld",l); 40 return 0; 41 }