CF1873E Building an Aquarium 题解

这题看到第一眼就是二分。

单调性

二分最关键的东西是单调性在哪。单调性是如果高度越高，需要的水就越多，高度越矮，要用的水越少。

不难得出代码：

check 函数：

int check(int mid){
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=max(0ll,mid-a[i]);
	}
	if(sum<=x)return sum;
	else return -1e9;
}

二分：

int l=0,r=1e18;
		while(l<=r){
			int mid=l+r>>1;
//			cout<<l<<" "<<r<<endl;
			if(check(mid)>=maxx){//如果这种写法就要是大于等于。
				l=mid+1;//如果返回的sum是0就进不了if
				maxx=check(mid);
				ans=mid;
			}
			else{
				r=mid-1;
			}
		}

其实这题很简单，建议评黄。