题目：平面上有一个大矩形，其左下角坐标（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
输出
输出整数n，表示答案应该是直线 x=n。 如果必要的话，x=R也可以是答案。
样例输入
1000
2
1 1 2 1
5 1 2 1
样例输出
5
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
struct jx{
    int x,y,w,h;
    float s;
    float area()
    {return w*h;}
};
int cmp(const jx &a,const jx &b)
{
    return a.x<b.x;
}
jx xjx[10001];
int R,n,mid,temp;
long long l,r,xx;
bool bo;
int sum(int xx)
{
    float area1=0,area2=0;
    bo=0;mid=0;
    for(int i=1;i<=n;i++)
    {if(xjx[i].x+xjx[i].w<=xx)
    {
     area1+=xjx[i].s;
     mid=i;
     }
    if(xjx[i].x>xx) area2+=xjx[i].s;
    if(xjx[i].x<xx&&xjx[i].x+xjx[i].w>xx)
    {
     area1+=(xx-xjx[i].x)*xjx[i].h;
     area2+=(xjx[i].x+xjx[i].w-xx)*xjx[i].h;
     bo=1;
     }
     }
     if(area1>area2) return 1;
     else if(area1<area2)return 2;
     else     return 0;
}

int main()
{   
    freopen("jx1.in","r",stdin) ;
    freopen("jx1.out","w",stdout);
    cin>>R>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>xjx[i].x>>xjx[i].y>>xjx[i].w>>xjx[i].h;
        xjx[i].s=xjx[i].area();
        }
    sort(xjx+1,xjx+n+1,cmp);
    l=xjx[1].x;
    r=xjx[n].x+xjx[n].w;
    while(l+1<=r)
    {
        xx=(l+r)/2;
        temp=sum(xx);
        if(temp==1) r=xx-1;
        else if(temp==2) l=xx+1;
        else  break;
        }
    if(bo==1) cout<<xx;   
    else cout<<xjx[mid+1].x;
    fclose(stdin);fclose(stdout);
    return 0;
}

[此贴子已经被作者于2016-8-16 14:16编辑过]

这道题在openjudge里面为什么提示答案错误？可是在编译器里运行结果是对的
------ 这里面有逻辑关系吗？起码测试用例就不一样。

代码一坨……，随便看一眼，freopen("jx1.in","r",stdin);也不知道是openjudge要求的，还是你自己写着玩的

算法应该很简单吧
从左往右，最多遍历一次即可，当 差值变大 时退出
若从右往左，也是最多遍历一次即可，当 差值不变小 时退出
求差值的话，不需要求出两边的面积，因为左右总面积是不变的， 差值 = abs( 左边面积 - (总面积-左边面积) )

顺次遍历可以在求面积上优化，但二分查找也不错
只有两个都写一遍才知道谁最快

想到一个新方法：
先将二维压成一维，然后从最左和最右两边出发，若左边“累加和”不大于右侧的累加，则左边向右移动一格；否则，右边向左移动一格。

明白了，谢谢！

#include <stdio.h>

int main( void )
{
    static unsigned line[1000000] = { 0 };

    unsigned R;
    scanf( "%u", &R );

    unsigned N;
    scanf( "%u", &N );
    while( N-- )
    {
        unsigned L, T, W, H;
        scanf( "%u%u%u%u", &L, &T, &W, &H );
        while( W-- )
            line[L+W] += H;
    }

    unsigned a=0, b=R;
    unsigned long long asum=0, bsum=0;
    while( a != b )
    {
        if( asum==bsum || line[a]==0 || asum<bsum+line[b-1] )
            asum += line[a++];
        else
            bsum += line[--b];
    }

    printf( "%u\n", a );
    return 0;
}

[此贴子已经被作者于2016-8-17 09:14编辑过]

用二分法写了一个，速度不是最快的
在网上看到别人写的代码 http://
我用
测试，此人的程序输出1，而结果应该是9

#include <stdio.h>

// 小矩形结构体
struct area
{
    unsigned L, W, H; // 左边x坐标、宽、高
};

// 以x=mid分割，返回 左边面积-右边面积
long long foo( const struct area* s, unsigned n, unsigned mid, long long total )
{
    long long left = 0;
    for( const struct area* p=s; p!=s+n; ++p )
    {
        if( p->L < mid )
        {
            if( p->L + p->W <= mid )
                left += p->W * p->H;
            else
                left += (mid-p->L) * p->H;
        }
    }
    return left-(total-left);
}

// 从from往右，搜寻无小矩形的最右位置
unsigned bar( const struct area* s, unsigned n, unsigned from, unsigned r )
{
    unsigned ret = r;
    for( const struct area* p=s; p!=s+n; ++p )
    {
        if( p->L<=from && p->L+p->W>from )
            return from;

        if( p->L>from && p->L<ret )
            ret = p->L;
    }
    return ret;
}

int main( void )
{
    unsigned R, N;
    struct area s[10000];
    long long total = 0;
    {
        scanf( "%u", &R );
        scanf( "%u", &N );
        for( unsigned i=0; i!=N; ++i )
        {
            scanf( "%u%*u%u%u", &s[i].L, &s[i].W, &s[i].H );
            total += s[i].W * s[i].H;
        }
    }

    unsigned a = 0;
    for( unsigned b=R; a!=b; )
    {
        long long m = foo( s, N, (a+b)/2, total );

        if( m == 0 )
            a=(a+b)/2, b=a;
        else if( m < 0 )
            a = (a+b)/2 + 1;
        else
            b = (a+b)/2;
    }
    printf( "%u\n", bar(s,N,a,R) );

    return 0;
}

谢谢！刚看到评分方法，和以前不同了，找了长时间。