题意：
有一块R*R的土地，上面有n个矩形，告诉你左下角的坐标和长和宽，矩形不会超过土地的边界
现在要用一条竖直分割线，把土地分成两个部分，要求：
A：左右两块土地，矩形面积和尽可能接近，而且左边的矩形面积不小于右边
B：在满足A的基础上，左边的土地面积尽可能的大
看到题目：很容易想到二分！
那为什么这个题现场很多人过不了呢（我这种菜都不知道怎么二分）
第一遍二分：
求得面积相等的（如果有的话，最左边的点）
在二分的过程中，最后的结束必定是到了R+1==L的时候
所以，L点必定是当前矩形面积最接近的点
第二遍二分：
因为我们要在矩形面积尽可能接近的基础上，让左边的土地面积尽可能的大
那么，在第一遍二分的基础上（已经得到了左边的最优的矩形面积）
再次二分
此时的R最终就会是答案（因为如果再过去1格，要么就过了R*R的边界，要么就打破了矩形面积最接近的条件）
代码如下：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<stdlib.h>
using namespace std;
#define LL long long
const int maxn=1e4+50;
int t,N,R,L[maxn],T[maxn],W[maxn],H[maxn];
LL S;
LL get(int x){
LL ret=0;
for(int i=0;i<N;i++)
ret+=1LL*H[i]*max(min(W[i],x-L[i]),0);
return ret;
}
int solve(){
LL tmp;
int l=0,r=R,mid;
while(l<=r){
int mid=(l+r)>>1;
tmp=get(mid);
if (tmp>=S-tmp) r=mid-1;
else l=mid+1;
}
tmp=get(l);
//cout<<l<<" "<<r<<endl;
l=0,r=R;
while(l<=r){
mid=(l+r)>>1;
if (get(mid)>tmp) r=mid-1;
else l=mid+1;
}
return r;
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&t);
for(int Case=1;Case<=t;Case++){
S=0;
scanf("%d%d",&R,&N);
for(int i=0;i<N;i++){
scanf("%d%d%d%d",&L[i],&T[i],&W[i],&H[i]);
S+=1LL*W[i]*H[i];
}
printf("%d\n",solve());
}
return 0;
}
重要的是注释的那句代码
贴几个有用的Hack数据：
看了这些数值就会明白刚才的两个二分为什么是哪些输出的答案了
8
100000
1
1 1 50000 1
100000
2
1 1 1 1
9999 9999 1 1
100000
2
2 2 1 1
9999 9999 1 1
1000000
2
1 1 1 1
99999 99999 1 1
1000
2
1 1 2 1
5 1 2 1
1000
1
1 1 2 1
1000000
1
999998 1 2 1
1000000
1
999998 1 1 1
京公网安备 11010502036488号