矩形分割

题意

选择整数竖线 $x=k$ 分割若干互不重叠的小矩形，使左侧面积不少于右侧、面积差最小；同样最优时取左侧区域最大的竖线位置。

思路

对一个给定的 $x$ ，每个矩形对左侧的贡献是 max(0, min(宽, x - 左边界)) * 高，相加得到单调不减的左侧面积。先二分左侧面积首次达到总面积一半的位置，这给出最小可行面积；若这一面积在一段横坐标上不变，再二分到这段平台最右端，满足题目的第二个要求。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34square_side = int(input())
rectangle_count = int(input())
rectangles = [tuple(map(int, input().split())) for _ in range(rectangle_count)]


def left_area(x: int) -> int:
    area = 0
    for left, _, width, height in rectangles:
        area += max(0, min(width, x - left)) * height
    return area


total_area = sum(width * height for _, _, width, height in rectangles)

# 先找左侧面积首次不少于右侧面积的位置。
low, high = 0, square_side
while low < high:
    middle = (low + high) // 2
    if left_area(middle) * 2 >= total_area:
        high = middle
    else:
        low = middle + 1

minimum_left_area = left_area(low)
# 同样的最小面积可能对应多个整数横坐标，取其中最大的一个。
low, high = low, square_side
while low < high:
    middle = (low + high + 1) // 2
    if left_area(middle) <= minimum_left_area:
        low = middle
    else:
        high = middle - 1

print(low)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/* 
 * 进行两次 二分 
 *  
 *  第一次 满足条件的左边小矩形的面积s
 *  第二次 第一次 >s 时的k值
 *
 * */

#include <bits/stdc++.h>
using namespace std;


int r;
int n;
struct _rect{
    int l,r,w,h;
    int m;
};

typedef long long ll;
_rect rect[10005];

void check(int k,ll &l, ll &r){
     r = 0;
     l = 0;
    
    int i;
    for(i=1;i<=n;i++){
        if( rect[i].l + rect[i].w <= k)
            l += rect[i].m;
        else if ( rect[i].l >= k)
            r += rect[i].m;
        else {
            l += (k- rect[i].l)* rect[i].h;
            r += (rect[i].l+ rect[i].w-k)* rect[i].h;
        }
    }
}

void init(){
    scanf("%d%d",&r,&n);
    int i;
    for (i=1;i<=n;i++){
        scanf("%d%d%d%d",&rect[i].l,&rect[i].r,&rect[i].w,&rect[i].h);
        rect[i].m  = rect[i].w * rect[i].h;
    }
}

long long first_ge(int l,int r){
    ll left,right;
    while(l < r){
        int m = (l+r) >> 1;
        check(m, left, right);
        if( left < right){
            l = m+1;
        }
        else
            r = m;
    }
    check(l, left, right);
    return left;
}

int first_g(int l,int r,long long rect_m){
    ll left,right;

    while( l < r){
        int m = (l+r) >> 1;
        check(m,left,right);
        if( left <= rect_m)
            l = m+1;
        else
            r= m;
    }
    return l;
}
int main(){
    init();
    long long m;
    m = first_ge(0,r);
    //printf("%d\n",m);
    int k = first_g(0, r+1,m);
    if( k > 0)
        printf("%d",k-1);
    else
        printf("0");
    return 0;
}

复杂度

每次面积计算为 $O(n)$ ，两次二分共 $O(n \log R)$ ，空间复杂度为 $O(n)$ 。

总结

面积随竖线右移单调不减，因此“最小达到目标”和“平台最右端”都可二分。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结