04136: 矩形分割

binary search, http://cs101.openjudge.cn/practice/04136

平面上有一个大矩形，其左下角坐标（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也可以是答案。

样例输入

样例输出

python

'''
1）题面要求：要使得大矩形在直线左边的的面积尽可能大。所以如果当前位置的小矩形高度为0，
则将位置向右移动。
2）逻辑首先计算每一列的小矩形的面积（宽度是1）在数组a中的高度分布，然后使用二分搜索
找到最优的直线位置，最后从最优位置开始向右搜索第一个高度不为0的小矩形位置。
最终输出的结果是一个最优的直线位置。
'''
R = int(input())
a = [0] * R
n = int(input())
for i in range(n):
	L, T, W, H = map(int, input().split())
	for j in range(L, L + W):
		a[j] += H
le = 0
ri = R
while True:
	if le >= ri:
		break
	else:
		mi = (le + ri) // 2
		x = sum(a[:mi])
		y = sum(a[mi:])
		if x >= y:
			ri = mi
		else:
			le = mi + 1
while True:
	if le == R:
		print(le)
		break
	elif a[le] == 0: #如果当前位置的小矩形高度为0，则将位置向右移动。
		le += 1
	else:
		print(le)
		break

04136: 矩形分割 ​

04136: 矩形分割