月度开销

题意

将连续的每天开销划分为至多 $M$ 个连续财政周期，最小化其中最大周期的开销。

思路

二分最大允许开销 limit。从前向后尽量把当天放进当前周期，若会超过 limit 就新开一个周期；这种贪心在给定上限下使用的周期数最少。若周期数不超过 $M$ ，说明该上限可行。

代码

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
25day_count, month_count = map(int, input().split())
expenses = [int(input()) for _ in range(day_count)]


def can_arrange(limit: int) -> bool:
    used_months = 1
    current_sum = 0
    for expense in expenses:
        if current_sum + expense > limit:
            used_months += 1
            current_sum = expense
        else:
            current_sum += expense
    return used_months <= month_count


low, high = max(expenses), sum(expenses)
while low < high:
    middle = (low + high) // 2
    if can_arrange(middle):
        high = middle
    else:
        low = 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#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n,m;
int a[maxn];

bool check(int val) {
    int cnt = 0;
    int sum =0;
    for(int i =1;i<=n;i++){
        if( sum + a[i] > val) {
            cnt++;
            sum = a[i];
            if( sum > val) return false; // 一件物品都装不下
        } else {
            sum += a[i];
        }
    }
    cnt++;
    return cnt <=m;
}

// bs = binary search
int bs_find(int l,int r) {
    while(l < r) {
        int mid = (l+r) >> 1;
        if( check(mid) ) { // 红色
            r = mid;
        } else { // 蓝色
            l = mid+1;
        }
    }
    return l;

}


int main(){
    cin >> n >> m;
    for(int i =1;i<=n;i++){
        cin >> a[i];
    }
    
    int pos = bs_find(1,10000 * 100000+1);
    cout << pos << endl;
    return 0;
}

复杂度

时间复杂度为 $O(n \log S)$ ，其中 $S$ 是所有开销之和；空间复杂度为 $O(n)$ 。

总结

“最小化最大值”常转化为“给定上限是否可行”的二分判定。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结