博客

平面上有一个大矩形，其左下角坐标（

0

，

0

），右上角坐标（

R,R)

。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于

y

轴的直线

x=k

（

k

是整数

)

，使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。并且，要使得大矩形在直线左边的的面积尽可能大。注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。

1000
2
1 1 2 1
5 1 2 1

样例输出

5

一道二分水题，虽然表面上 Hard，理解题意后就好了。。。

然而我还是卡了半个小时，吃枣药丸。。。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 100010
using namespace std;
int r,n,m,l=0,mid;
long long s1,s2,s;
bool flag=false;
struct node{
       long long x,y,w,h;
}a[MAXN];
inline int read(){
       int date=0,w=1;char c=0;
       while(c!='-'&&(c<'0'||c>'9'))c=getchar();
       if(c=='-'){w=-1;c=getchar();}
       while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
       return date*w;
}
int main(){
    r=read();n=read();
    m=r;
    for(int i=1;i<=n;i++){a[i].x=read();a[i].y=read();a[i].w=read();a[i].h=read();}
    while(l<=r){
                mid=l+r>>1;
                flag=true;
                s1=s2=0;
                for(int i=1;i<=n;i++){
                        if(a[i].x<mid){
                                     if(a[i].x+a[i].w<=mid)s1+=(long long)a[i].w*a[i].h;
                                     else{
                                          s1+=(long long)a[i].h*(mid-a[i].x);
                                          s2+=(long long)a[i].h*(a[i].x+a[i].w-mid);
                                          flag=false;
                                          }
                                     }
                        else s2+=(long long)a[i].w*a[i].h;
                        }
                if(s1<s2)l=mid+1;
                else if(s1>s2){
                     r=mid-1;
                     if(s){printf("%d\n",s);return 0;}
                     }
                else if(s1==s2){
                     if(flag){l+=2;s=mid;}
                     else{printf("%d\n",mid);return 0;}
                     }
                }
    if(s1<s2)mid++;
    if(s2)printf("%d\n",mid);
    else printf("%d\n",m);
    return 0;
}