题意分析

题目给定一个长度为 $N$ 的整数序列 $\{a_n\}$，要求将其分割成若干连续的子序列（即“部分”），使得每一部分的和不超过给定的整数 $M$。目标是找到一种分割方式，使得每一部分的最大值之和最小。如果无法满足分割条件（比如某个元素本身超过 $M$），则输出 $-1$。

解题思路

1. 动态规划状态定义
   • 设 $f[i]$ 表示前 $i$ 个元素分割后的最小最大值之和。
2. 转移方程
   • $f[i] = \min(f[j] + \max(a[j+1..i]))$，其中 $sum(a[j+1..i]) \leq M$。
3. 优化方法
   • 滑动窗口：维护一个窗口 $[k, i]$，使得 $sum(a[k..i]) \leq M$。
   • 单调队列：维护当前窗口的最大值，确保队列头部是当前窗口的最大值。
   • 平衡树（multiset）：存储可能的 $f[j] + \max(a[j+1..i])$ 值，方便快速查询最小值。

实现过程

1. 输入处理
   • 检查是否存在单个元素 $a[i] > M$，如果存在直接输出 $-1$。
2. 前缀和计算
   • 计算前缀和数组 $sum$，方便快速计算子序列和。
3. 滑动窗口维护
   • 使用指针 $k$ 维护窗口左边界，确保 $sum[i] - sum[k] \leq M$。
4. 单调队列优化
   • 维护一个队列 $q$，存储可能成为最大值的候选下标。
   • 队列头部是当前窗口的最大值，队列尾部是可能被当前元素 $a[i]$ 覆盖的较小值。
5. 平衡树维护最小值
   • 使用 multiset 存储 $f[j] + \max(a[j+1..i])$，方便快速查询最小值。
6. 动态规划更新
   • 更新 $f[i]$ 为队列头部对应的最大值加上 $f[k]$，或者从 multiset 中取最小值。

代码实现

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;

const int maxn = 100010;
int q[maxn], a[maxn], n;
LL m, sum[maxn], f[maxn];

int main() {
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    multiset<int> s;
    int k = 0, l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > m) { printf("-1"); return 0; }
        while (sum[i] - sum[k] > m) k++;
        while (l <= r && q[l] <= k) {
            if (l < r) s.erase(a[q[l + 1]] + f[q[l]]);
            l++;
        }
        while (l <= r && a[q[r]] <= a[i]) {
            if (l < r) s.erase(a[q[r]] + f[q[r - 1]]);
            r--;
        }
        q[++r] = i;
        if (l < r && i > q[r - 1])
            s.insert(a[i] + f[q[r - 1]]);
        int tmp = *s.begin();
        f[i] = a[q[l]] + f[k];
        if (l < r && tmp < f[i]) f[i] = tmp;
    }
    printf("%lld", f[n]);
    return 0;
}