03:矩形分割 (二分）

描述

平面上有一个大矩形，其左下角坐标（0，0），右上角坐标（R,R)。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于y轴的直线x=k（k是整数) ，使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。并且，要使得大矩形在直线左边的的面积尽可能大。注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。

输入

第一行是整数R，表示大矩形的右上角坐标是(R,R) (1 <= R <= 1,000,000)。
接下来的一行是整数N,表示一共有N个小矩形(0 < N <= 10000)。
再接下来有N 行。每行有4个整数，L,T, W 和 H, 表示有一个小矩形的左上角坐标是(L,T),宽度是W，高度是H (0<=L,T <= R, 0 < W,H <= R). 小矩形不会有位于大矩形之外的部分。

输出

输出整数n，表示答案应该是直线 x=n。如果必要的话，x=R也可以是答案。

样例输入

样例输出

5

分析：（错误）先想到前缀和，然后暴力，（正解）突然想到他们可以平行，就二分，然后，二分的答案不一定是最优答案，需要将直线右移，知道不能移动。
　　　　移动的过程没想到怎么去最优化，采取保险做法，暴力右移。

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define mem(s,t) memset(s,t,sizeof(s))
#define pq priority_queue
#define pb push_back
#define fi first
#define se second
#define ac return 0;
#define ll long long
#define rep(xx,yy) for(int i=xx;i<=yy;i++)
#define TLE std::ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);   cout.precision(10);
const double eps = 1e-14;
const int mxn = 1e3;
string str;
ll r,n,mx=-1;
struct node
{
    ll x,y,r,h;
    ll area;
} no[10000];
ll check( ll mid)
{
    ll larea = 0, rarea = 0;
    for(int i=1; i<=n; i++)
    {
        if( no[i].x>=mid )
            rarea += no[i].area;
        else if(no[i].r<=mid)
            larea += no[i].area;
        else
        {
            larea += (mid-no[i].x)*no[i].h;
            rarea += (no[i].r-mid)*no[i].h;
        }
    }
    return larea-rarea;
}
int main()
{
    TLE;
    cin>>r;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>no[i].x>>no[i].y>>no[i].r>>no[i].h;
        no[i].area = no[i].r*no[i].h;
        no[i].r += no[i].x;
    }
    if(n==1&&no[n].r-no[n].x==1)
        {cout<<r<<endl;return 0;}
    ll l = 0,ok=0;
    while(l<r)
    {
        ll mid = (l+r)>>1;
        if(!check(mid))
            {ok = mid;break;}
        else if( check(mid)<0 )
            l = mid+1;
        else
            r = mid;
    }
    if(ok)
    {
        while(ok<=r && check(ok)==check(ok+1))
            ok++;
        cout<<ok<<endl;
    }
    else
    {
        while(l<=r && check(l)==check(l+1))
            l++;
        cout<<l<<endl;
    }
    return 0;
}

所遇皆星河