洛谷P1873 砍树二分答案

洛谷P1873 砍树

二分答案

与原来的二分差不多
O(n) 判断当然也可以小优化一下将 h 从高到低排序
这题要用long long 感觉不大保险，于是全部都加了long long

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <string>
 7 #include <iomanip>
 8 #include <iostream> 
 9 #define ll long long 
10 using namespace std ; 
11 
12 inline ll read() 
13 {
14     char ch = getchar() ; 
15     ll x = 0 , f = 1 ; 
16     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; }
17     while(ch>='0'&&ch<='9') { x = x*10 + ch - 48 ; ch = getchar() ; } 
18     return x*f ; 
19 }
20 
21 const int maxn = 1000011 ; 
22 ll n,m,l,r,mid ;
23 ll h[maxn] ; 
24 
25 inline bool check(ll x) 
26 {
27     ll sum = 0 ;
28     for(int i=1;i<=n;i++) 
29         if(h[ i ]>x) sum = sum + h[ i ]-x ; 
30     return sum >= m ;
31 }
32 
33 int main() 
34 {
35     n = read() ;   m = read() ;  
36     for(int i=1;i<=n;i++) 
37         h[ i ] = read(),r = max(r,h[ i ]) ;  
38     l = 0 ;  
39     while( l < r ) 
40     {
41         mid = (l+r+1) / 2 ; 
42         if( check(mid) ) 
43             l = mid ; 
44         else 
45             r = mid - 1 ; 
46     }
47     printf("%lld
",l ) ; 
48     return 0 ; 
49 }

洛谷P1873 砍树 二分答案

洛谷P1873 砍树二分答案