ACM 2015 亚洲区域赛北京赛区A题（二分）

该题方法就是二分， 二分R，然后在判断函数中判断在枚举点左边的绿洲面积。  这样做的复杂度是O(nlogR)。

但是一开始WA了一发，后来才发现原来是因为有这样的数据：一块很大的沙漠中只有一个边长为1的小正方形绿洲。这样的数据答案是R。  所以我二分出来之后再向右推一下，直到不符合条件为止。

下面是我AC代码， 二分求的上界，求下界应该更快，请读者自己实现。

细节参见代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 10000+5;
int T,n,m,R;
ll sum;
struct node {
    ll x,y,w,h;
    bool operator < (const node& rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
}a[maxn];
bool D(int m) {
    ll tot =  0;
    for(int i=0;i<n;i++) {
        if(a[i].x+a[i].w <= m) {
            tot += a[i].w*a[i].h;
        }
        else if(a[i].x >= m) break;
        else if(a[i].x <= m && m <= a[i].x+a[i].w) {
            tot += (m-a[i].x)*a[i].h;
        }
    }
    if(tot >= sum-tot) return true;
    else return false;
}
ll hehe(int m) {
    ll tot =  0;
    for(int i=0;i<n;i++) {
        if(a[i].x+a[i].w <= m) {
            tot += a[i].w*a[i].h;
        }
        else if(a[i].x >= m) break;
        else if(a[i].x <= m && m <= a[i].x+a[i].w) {
            tot += (m-a[i].x)*a[i].h;
        }
    }
    return tot;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&R,&n);
        sum = 0;
        for(int i=0;i<n;i++) {
            scanf("%I64d%I64d%I64d%I64d",&a[i].x,&a[i].y,&a[i].w,&a[i].h);
            sum += a[i].w*a[i].h;
        }
        sort(a,a+n);
        int l = 0, r = R+10, m;
        while(r > l) {
            m = (l+r)/2;
            if(D(m)) r = m;
            else l = m+1;
        }
        ll cur = hehe(r);
        while(true) {
            if(r > R) { r = R; break; }
            if(hehe(r) == cur) r++;
            else { r--; break; }
        }
        printf("%d\n",r);
    }
    return 0;
}