Monthly Expense

题目解析

1. 题目抽象与理解

首先，我们把问题抽象化：

有一个长度为 $N$ 的数组 a，其中 a[i] 表示第 $i$ 天的支出。
需要将这个数组划分成恰好 $M$ 个连续的段（每个段是一个「fajo 月」）。
设第 $k$ 个段的元素和为 S_k，我们要最小化 max(S_1, S_2, ..., S_M)。

这就是经典的 「划分型二分」，也叫 「最小化最大子数组和」 问题。它类似于 LeetCode 的「410. Split Array Largest Sum」。

2. 核心思路：二分答案

观察答案 $X$ 一定落在区间 [max_day, total_sum] 内：

下界 max_day = max(a[i])：如果 $X$ 小于单日最大开销，那么包含这一天的月份肯定装不下。
上界 total_sum = sum(a[i])：如果只用一个月（ $M=1$ ），总开销就是全部加起来。

单调性 当 $X$ 越大，越容易用不超过 $M$ 个月份装下所有天数；反之， $X$ 越小，需要的月份越多。因此存在临界值 $X^*$ ：

当 $X \ge X^*$ 时，可以划分成 $\le M$ 个月份。
当 $X < X^*$ 时，需要 $> M$ 个月份。

这个临界值 $X^*$ 就是我们要找的最小化的最大开销。

算法二分枚举 $X$ ，用 check(X) 判断是否能将数组划分成 不超过 $M$ 段，使得每段和都不超过 $X$ 。

如果 check(X) 为真，说明 $X$ 可能可以更小，令 right = X。
如果 check(X) 为假，说明 $X$ 太小，令 left = X + 1。

贪心策略 从左到右扫描，在不超过上限 mid 的前提下，尽可能多地把天数塞进当前月份。这是一种「能装就装」的贪心，其正确性在于：

每个段都是连续且不可重排：我们必须按顺序装填。
越晚分段越好：如果把一些天提前分到下一月，只会让当前月变小、下一月变大，可能导致后面的分段更难满足 mid 的限制。所以尽可能装满是最优策略。

时间复杂度： $O(N)$ 每次验证。

为什么这种贪心是正确的？

反证法思路：假设存在某种最优划分方式，在某个位置我们本可以继续将 a[i] 放入当前段（当前段和 + a[i] ≤ mid），但我们却选择新开一段。那么：

新开段的第一天是 a[i]，当前段的和不变。
这会导致后面的天数更难分配到有限的段中（因为我们浪费了一次分段的机会）。

因此，尽可能装满当前段 的贪心策略不会比任何最优解差。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-15 22:09:50
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn];
int max_spend;

//oisnip_beginbinary_search.cpp
//这是最快的写法
ll mid(ll l,ll r) { return (l+r) >> 1; }

//检查pos位置的值是否符合要求
bool check(ll money){
    int cnt = 0;
    ll sum = 0;
    for(int i =1;i<=n;i++) {
        if( sum + a[i] <= money) {
            sum += a[i];
        }
        else {
            cnt++;
            sum = a[i];
        }
    }
    cnt++;
    return cnt <= m;
}

//bs_find = binary search find
// 返回第一个满足条件的位置
// 如果所有的值都不满足条件,返回r, 
// !!! r位置对应的是Guard,一个虚拟的位置,保证一定各满足check
// !!! 写题目的时候一定要注意r的值,通常是n+1
// 保障初始区间[l,r],r一定是满足的,通常r = n+1
ll  bs_find(ll l,ll r) {
    while( l < r) {
        int m = mid(l,r);
        if( check(m)) //成立
            r = m;
        else //不成立,抛弃左半边
            l = m+1;
    }
    return l ;
}
//oisnip_end

void init(){
    std::cin >> n >> m;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
        if( max_spend < a[i])
            max_spend = a[i];
    }

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    ll pos = bs_find(max_spend, 1e9);
    std::cout << pos << "\n";
    
    return 0;
}

目录

题目解析

1. 题目抽象与理解

2. 核心思路：二分答案

代码