求助,二分只过了第一个测试点
查看原帖
求助,二分只过了第一个测试点
1051616
duck_lite楼主2024/8/12 20:24

怀疑是l,r边界的问题

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 +5;
ll T=0; 
ll n,m;
ll v[N]; 
bool check(ll mid){
	ll sum=0;
	for(ll i=1;i<=n;++i){
		if(v[i]>mid)sum+=v[i]-mid;
	}
	if(sum>m)return 1;//砍太多了
	else return 0;
	
} 
void solve(ll n){
	ll l=v[1]-1,r=v[n]+1;
	while(l+1!=r){
		ll mid=(l+r)>>1;
		if(check(mid)) l=mid;//砍得太多了 
		else r=mid;		 
	} cout<<r;
} 
int main() 
{	
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;++i){
		ll x;scanf("%lld",&x); 
		v[i]=x;
	} sort(v+1,v+1+n);//v数组存放树的高度

	solve(n) ;

    return 0;
}

Orz感谢dalao

2024/8/12 20:24
加载中...