二分法---矩形分割（容易忽略的极端情况）
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也可以是答案。
样例输入：
1000
2
1 1 2 1
5 1 2 1
【二分法---矩形分割（容易忽略的极端情况）】样例输出：
5
这道题最容易考虑不到的地方，就是所有矩形都是宽度为1，且在处在同一列上，此时答案应该是R！
例如：输入为
10000
1
1 1 1 1
输出应该是10000 ！
#include
#include
#include
#define num 10010
using namespace std;
struct Rectangle
{
long long L, T, W, H ;
};
Rectangle rectangle[num];
long long s[num], sum = 0;
long long R, N, s_left = 0, s_right = 0;
long long Search(long long a) {
s_left = 0, s_right = 0;
for (int i = 0;
i < N;
++i){
if (a >= rectangle[i].L + rectangle[i].W)
s_left += rectangle[i].W*rectangle[i].H;
else if (a <= rectangle[i].L)
s_left += 0;
else
s_left += (a - rectangle[i].L)*rectangle[i].H;
}
s_right = sum - s_left;
return s_left - s_right;
}int main()
{
cin >> R >> N;
for (int i = 0;
i < N;
++i) {
cin >> rectangle[i].L >> rectangle[i].T >> rectangle[i].W >> rectangle[i].H;
sum += rectangle[i].W*rectangle[i].H;
} long long left = 0, right = R, mid;
while (left < right - 1) {
mid = left + (right - left) / 2;
long long s_dif = Search(mid);
if (s_dif > 0)
right = mid;
else if (s_dif <= 0)
left = mid;
}
long long ans;
s_left = 0, s_right = 0;
if (Search(left) < 0)
ans = right;
else if (Search(left) < Search(right))
ans = left;
else if (Search(left) >= Search(right))
ans = right;
if (Search(ans) == sum)
ans = R;
cout << ans;
return 0;
}
推荐阅读
- EffectiveObjective-C2.0|EffectiveObjective-C2.0 笔记 - 第二部分
- 遇到一哭二闹三打滚的孩子，怎么办┃山伯教育
- 赢在人生六项精进二阶Day3复盘
- 2019年12月24日
- 陇上秋二|陇上秋二 罗敷媚
- 一百二十三夜，请嫁给我
- 迷失的世界（二十七）
- 我要我们在一起（二）
- 基于|基于 antd 风格的 element-table + pagination 的二次封装
- (二)ES6第一节变量(let|(二)ES6第一节变量(let,const)