UVA 7261 Interesting Bsearch & Bsearch 二分

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5273
题目大意：给出一篇矩形区域，左下角为$[0,0]$[0,0]，右上角为$[1,1]$[1,1]，区域内有$n$n个绿洲，给出每个绿洲的左下角的坐标和这个绿洲的长度和高度，现在要找一个位置$pos$pos，在这个位置做一条平行于$y$y的直线把区域分成两部分，使得左半部分绿洲的面积大于等于右半部分且两者差距最小，在这个差距不变的情况下使左半部分土地的区域尽量大。

思路：二分找位置$pos$pos。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
#define eps 1e-6
using namespace std;
typedef long long ll;

const int maxn=1e4+5;

ll l[maxn],t[maxn],w[maxn],h[maxn],R;
int n;

ll check(ll mid)
{
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		if(l[i]+w[i]<=mid)
			ans+=w[i]*h[i];
		else if(l[i]<=mid&&l[i]+w[i]>mid)
			ans+=(mid-l[i])*h[i];
	}
	return ans;
}

int main()
{
	int tt;
	scanf("%d",&tt);
	while(tt--)
	{
		ll sum=0;
		scanf("%lld%d",&R,&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld%lld%lld",&l[i],&t[i],&w[i],&h[i]);
			sum+=w[i]*h[i];
		}
		++sum;
		sum/=2;
		ll tmp;
		ll L=1,r=R,mid;
		while(L<=r)
		{
			mid=L+r>>1;
			tmp=check(mid);
			if(tmp<sum)
				L=mid+1;
			else
				r=mid-1;
		}
		tmp=check(L);
		while(check(L)==tmp&&L<=R)
			++L;
		printf("%lld\n",L-1);
	}
	return 0;
}