题目链接：http://noi.openjudge.cn/ch0111/03/
一个二分的题目，估计是数据类型选择不当，折腾了好多天。所以，以后记得尽管使用long long类型数据呵呵
描述
平面上有一个大矩形，其左下角坐标（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也可以是答案。样例输入
1000 2 1 1 2 1 5 1 2 1
样例输出
5
我的思路：对解区间[0，R]做二分，查找可能的解。（假设每一次二分计算的中间点是解，然后做验证。然后在寻找更合理的解。）
注意：long long类型数据要使用%lld输入输出。
暂时还有一个疑惑，就是末尾的绝对值部分。（这个下面再提）
AC代码：
1 #include<stdio.h> 2 #include<math.h> 3 struct obj 4 { 5 long long left,top,w,h;//左上角横、纵坐标和宽、高值 6 long long rx;//右下角顶点的横坐标 7 long long s;//面积 8 }; 9 long long sigema(struct obj a[],int n,int mid) 10 { 11 int i; 12 long long sum1,sum2; 13 sum1=sum2=0; 14 for(i=0;i<n;i++) 15 { 16 if(a[i].rx<=mid) sum1+=a[i].s; //该矩形属左侧 17 else if(a[i].left>=mid) sum2+=a[i].s;//属右侧 18 else 19 { 20 sum1+=a[i].h*(mid-a[i].left); 21 sum2+=a[i].h*(a[i].rx-mid); 22 } 23 } 24 return sum1-sum2; 25 } 26 int main() 27 { 28 long long r,n,i; 29 struct obj a[10005]; 30 long long minx,maxx,mid,ans,maxx2; 31 long long temp,temp1,temp2; 32 33 scanf("%lld%lld",&r,&n); 34 for(i=0;i<n;i++) 35 { 36 scanf("%lld%lld%lld%lld",&a[i].left,&a[i].top,&a[i].w,&a[i].h); 37 a[i].s=a[i].w*a[i].h; 38 a[i].rx=a[i].left+a[i].w; 39 if(i==0) maxx2=a[i].rx; 40 else 41 { 42 if(a[i].rx>maxx2) maxx2=a[i].rx; 43 } 44 } 45 minx=0; 46 maxx=r; 47 while(minx+1<maxx)//需要二分枚举的答案是整数，所以可以用这个方式结束 48 { 49 mid=(minx+maxx)/2; 50 temp=sigema(a,n,mid); 51 if(temp>0) maxx=mid; 52 else if(temp<=0) minx=mid; 53 } 54 55 temp1=sigema(a,n,minx); 56 temp2=sigema(a,n,maxx); 57 /*if(fabs(temp1)<fabs(temp2)) ans=minx; 58 else ans=maxx;*/ 59 if( temp1<temp2) 60 { 61 if(temp1>=0) ans=minx; 62 else ans=maxx; 63 } 64 else if(temp1>temp2) 65 { 66 if(temp2>=0) ans=maxx; 67 else ans=minx; 68 } 69 else ans=maxx; 70 if(ans==maxx2) ans=r; 71 printf("%lld\n",ans); 72 return 0; 73 }
这个题目一直有一个疑惑。最开始的时候题目并未有提到有一个大矩形，题目的要求仅仅是“左边部分小矩形的面积之和不小于右边部分小矩形面积之和”。后来题目做了修改，增加了大矩形的约束。参看了别人的代码，也自己验证过，代码后面的if语句里面的绝对值竟然在修改题目后还可以通过。就是下面的语句：
if(fabs(temp1)<fabs(temp2)) ans=minx; else ans=maxx;
我一直都觉得这个语句只能起到约束题目的第一个条件（小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小），并不能够约束题目的第二个条件（要使得大矩形在直线左边的的面积尽可能大）。因为若是直接取绝对值，不能够保证哪一边的面积比较大，只是能够保证两边的面积差距尽量小。
所以，我在后面代码里面做了修改，用的是这样的代码：
1 if( temp1<temp2) 2 { 3 if(temp1>=0) ans=minx; 4 else ans=maxx; 5 } 6 else if(temp1>temp2) 7 { 8 if(temp2>=0) ans=maxx; 9 else ans=minx; 10 } 11 else ans=maxx;
另外，还要一个地方比较重要，那就是最后一个if语句。
1 if(ans==maxx2) ans=r;
