样例1如图,用二分法找出 $h$ 。因为 $h$ 可能很大,所以初始化的 $r$ 也开大一点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include<iostream> #include<algorithm> using namespace std; const int N=2e5+10;
typedef long long ll;
int nums[N]; int s[N];
int h; int n,x;
bool check(ll h) { ll water=x; for(int i=1;i<=n;i++) { if(h>nums[i]) { water=water-(h-nums[i]); }
if(water<0) { return true; } }
return false; }
int main() { int _; cin>>_; while (_--) { cin>>n>>x; for(int i=1;i<=n;i++) { cin>>nums[i]; }
ll l=0,r=4e9; ll ans; while (l<r) { ll mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } cout<<l-1<<endl; } return 0; }
|