03:矩形分割

本文主要是介绍03:矩形分割，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

03:矩形分割

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

一开始看题，既要左右面积差值最小又要大矩形左侧面积最大，像极了数学里高深的优化问题，难不成还得来个多元线性回归？！
不重叠，说明 要求大矩形左侧面积尽可能大，只是建立在 已经找到小矩形们左右面积差最小的位置 这一条件之上，如果找到的位置x可以向右移动并且不改变左右侧小巨星们的面积（怎么才能实现这一条件呢？自然是这个位置位于两个小矩形之间的留白处，那么就将x进一步向右调整到下一个小矩形的左侧，跨过整个留白区, 或者是跨国最后一个小矩形与大矩形右边界的留白区），这种操作可以视作两种情况，也可合二为一

		while(areaD(x)==areaD(x+1)&&x<a){
		x++;
	}//x可以取到大矩形右边界a 
	cout<<x;

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
	ll a;//大正方形右上角坐标 
	ll n;//n个小矩形
//int lx,ly,w,h;//每个小矩形左上角坐标和宽、高
//	int a[MAX][4];
	struct matrix{
		ll l,u,w,h;//左上宽高 
	}m[10001]; 
	ll Size=0;//总面积 
ll areaD(int x){
	ll leftS=0;
	for(int i=0;i<n;i++){
		if(m[i].l<x){
			if(m[i].l+m[i].w<=x)leftS+=m[i].w*m[i].h;
			else leftS+=(x-m[i].l)*m[i].h;
		}
	}
	ll differ=leftS-(Size-leftS);
	return differ;
}
ll search(int left,int right){
		ll mid;
		while(left<=right){
		mid=left+(right-left)/2;
		if(areaD(mid)>0)right=mid-1;
		else if(areaD(mid)<0)left=mid+1;
		else return mid;
	}
	return left;
}
int main(int argc, char** argv) {
	cin>>a>>n;
	for(int i=0;i<n;i++){
		cin>>m[i].l>>m[i].u>>m[i].w>>m[i].h;
		Size+=m[i].w*m[i].h;
	} 
	ll  x=search(0,a);
	while(areaD(x)==areaD(x+1)&&x<a){
		x++;
	}//x可以取到大矩形右边界a 
	cout<<x;
	return 0;
}

总而言之：
1、能找到面积相等的位置，就继续探寻是否能跨过一个留白区，找到满足“左侧面积 = =右侧面积”的最大整数值
2、对于右侧面积为0的：最终值 = 大矩形的边界 r
3、若不属于以上两种情况，就通过while(left<=right)这种二分寻找跳出循环后的left，就是使左右侧面积最接近的位置

还有一个迷惑问题，search函数中将else if改成if，结果惊人1000？？？

接下来关注到二分查找的细节

二分查找的截止判断条件

1. while(left<=right)……

2. while(left<right)……

3. while(left<right-1)……

   找到了mid倒无甚区别，，如果没找到还需要依赖left与right的final值来确定与所求值最接近的数据的一个范围
   NO.3：
   跳出循环后，left == right-1，left与right紧紧相邻
   需要二分枚举的答案是整数，所以可以用这个方式结束，
   像这题，还需要分别判断left 和 right哪个更能使左右小矩形们面积之差靠近
   并且在循环体内部
   if (sum>0) r=mid;
   else if (sum<=0) l=mid;
   else if (sum==0) {printf("%d",mid);return 0;}
   左右边界值的修改是这样进行的
   NO.1
   跳出循环后
   在循环内部这样修改边界值
   while(left<=right){
   mid=left+(right-left)/2;
   if(areaD(mid)>0)right=mid-1;
   else if(areaD(mid)<0)left=mid+1;
   else return mid;
   }
   return left;

   NO.2
   while(left<right)……
   在循环内部这样修改边界值
   if(leftS<=rightS) //为了尽量让k靠右，需要用小于等于
   {
   l=mid;
   }
   if(leftS>rightS) //为了尽量减少面积差
   {
   r=mid;
   }

   在循环体内部，可以进行最后一次二分进行判断
   if(r-l==1) //经过二分后的最后判断

   NO.1、2都默认跳出循环之后/最后一次循环中，left是最接近寻找的值
   如果mid可能包括要找的值和其他，那么修改边界值（目的是继续寻找边界，边界就要取上一次的mid

while(l<r){/*lower_pound()二分求下界*/
		mid=l+(r-l)/2;
		if(2*sa[mid]>=sa[R])r=mid;//必须如此，不可r=mid-1；亲测错误
		else l=mid+1;
	}
	return l;
}

 NO.1、2都默认跳出循环之后/最后一次循环中，left是最接近寻找的值
 也就是要寻找的值可能会出现在边界值里
 如果将NO.1的mid+/-1改成mid。将NO.2的mid+1改成mid，都会超时
 好的，乱了
 关于修改边值条件，到底是mid+/-1 还是 mid， 要回到二分法最初的思想，就是在target出现的更小的范围内继续二分，也就是说，接下来划定的范围无论如何一定要包括target 但是已经排除的范围不能再加到下一次二分的范围。
 这题target是areaD（mid）==0，或者是areaD（mid）>0的范围里取一个 最接近mid的
 
 一、
 每次二分都是奔着mid=0去的，因此mid不满足条件，就不用再加入下次二分的范围内
 最后一次二分，left==right=mid，mid还不满足条件，那必定是mid-1小于0，mid+1大于0，根据题意我们选的是后者
 这种二分方式，循环结束后left是比所求得target稍大得那个
 二、
 ，mid小于等于0包含了mid==0，mid也许就是最后的target，故需要加入下次二分的范围内。 每次二分其实是为了找到mid>0得最小mid去的，因此mid>0符合所求，故加入下一次二分范围。
 不同于NO3的是跳出循环后，mygod
 三、
 每次二分其实是为了找到mid>0得最小mid去的，因此mid>0符合所求，故加入下一次二分范围，mid小于等于0包含了mid==0，mid也许就是最后的target，故需要加入下次二分的范围内
 跳出循环后，left<right并相邻，并不知道谁更靠近target所以要判断比较

这篇关于03:矩形分割的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！