【GESP】C++五级练习题 luogu-P1182 数列分段 Section II

发表于 2026/01/11 更新于 2026/01/11

作者 OneCoder

次浏览 10 分钟阅读

GESP C++ 五级练习题，二分答案和贪心思想考点应用，五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1182 数列分段 Section II

题目要求

题目描述

对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。
将其如下分段：
\[[4\ 2][4\ 5][1]\]
第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。
将其如下分段：
\[[4][2\ 4][5\ 1]\]
第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。
并且无论如何分段，最大值不会小于 $6$。
所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。
第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

输入输出样例 #1

输入 #1

5 3
4 2 4 5 1

输出 #1

6

说明/提示

对于 $20\%$ 的数据，$N\leq 10$。

对于 $40\%$ 的数据，$N\leq 1000$。

对于 $100\%$ 的数据，$1\leq N\leq 10^5$，$M\leq N$，$A_i < 10^8$，答案不超过 $10^9$。

题目分析

本题主要考察 二分答案 与贪心算法。

题目要求将数列划分成 $M$ 段，求“每段和的最大值”的最小值。每当我们看到 “最大值最小” 或 “最小值最大” 这类字眼时，首先应该想到的就是 二分答案。

解题思路：

确定解的范围（二分区间）：
- 下界 $L$：数列中最大的元素值（$\max(A_i)$）。因为每一段至少包含一个元素，且元素均为正整数，所以任何一段的和都不可能小于数列中的最大单个元素。
- 上界 $R$：数列所有元素的和（$\sum A_i$）。这是最极端的情况，即把整个数列分成 1 段。
二分枚举答案：
- 我们在这个区间 $[L, R]$ 内进行二分查找。
- 设当前尝试的答案为 $mid$（即假设每段和的最大值不超过 $mid$）。
- 我们需要一个 check(mid) 函数来验证这个 $mid$ 是否可行。
贪心判定策略 (check 函数)：
- 目标：判断在“每段和 $\le mid$”的限制下，最少需要分成多少段？
- 策略：为了让分出的段数尽可能少，我们应该贪心地让每一段尽可能长（和尽可能接近 $mid$）。
- 过程：从左到右遍历数列，累加当前段的和。如果不超过 $mid$，就继续加；如果加上下一个数会超过 $mid$，说明这一段装满了，必须截断，开启新的一段（段数计数器 $+1$）。
- 结论：
  - 如果计算出的段数 $\le M$，说明这个 $mid$ 限制比较宽松，我们还可以尝试更小的答案（r = mid - 1，并记录当前可行解）。
  - 如果计算出的段数 $> M$，说明这个 $mid$ 限制太死了，导致每一段装得太少，分出的段数过多，必须增大 $mid$（l = mid + 1）。

时间复杂度： 二分查找的次数约为 $\log(\sum A_i)$，每次 check 需要遍历整个数列 $O(N)$。因此总时间复杂度为 $O(N \log(\sum A_i))$，对于 $N \le 10^5$ 的数据规模，完全可以在时限内通过。

示例代码

  
/**
 * P1182 数列分段 Section II
 *
 * 题目要求：
 * 将一个长度为 N 的数列分成 M 段，要求每段连续。
 * 目标是让“每段和的最大值”最小。
 *
 * 思路分析：
 * 这是一个典型的“二分答案”（Binary Search on Answer）问题。
 * 我们二分枚举“每段和的最大值”这一可能得答案（设为 x）。
 * 然后检查：如果每段和最大不超过 x，最少需要分成几段？
 * - 如果最少分成的段数 <= M，说明 x 还可以更小（或者 x 正好），尝试往左搜。
 * - 如果最少分成的段数 > M，说明 x 太小了，塞不下，需要往右搜。
 */

#include <climits>
#include <cmath>
#include <iostream>

// 使用 long long (ll) 是为了防止和溢出。
// 虽然 N <= 10^5, A_i <= 10^8，但总和可能达到 10^13，超过 int (2*10^9) 范围。
typedef long long ll;
const int MAXN = 100005;
ll a[MAXN];

/**
 * 检查函数 check(limit)
 * 功能：判断当每段和的最大值不超过 limit 时，最少需要分多少段。
 *
 * 贪心策略：
 * 尽可能把更多的数字塞进当前这一段，直到塞不下（和超过 limit）为止，
 * 然后开启新的一段。这样得到的段数是最少的。
 */
bool check(int n, int m, ll limit) {
    int seg = 1;     // 当前是第几段（初始为第1段）
    ll cur_sum = 0;  // 当前这一段的累加和
    for (int i = 1; i <= n; i++) {
        // 如果加上当前数字 a[i] 会超过限制 limit
        if (cur_sum + a[i] > limit) {
            seg++;           // 必须开启新的一段
            cur_sum = a[i];  // 新的一段从 a[i] 开始
        } else {
            cur_sum += a[i];  // 否则加到当前段里
        }
    }
    // 如果最少需要的段数 seg <= m，说明 limit 是可行的（甚至可能偏大），返回
    // true
    return seg <= m;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    ll sum = 0;
    ll l = 0;  // 二分下界：答案至少是数列中的最大值（因为一段至少包含一个数）
    for (int i = 1; i <= N; i++) {
        std::cin >> a[i];
        sum += a[i];
        l = std::max(l, a[i]);
    }

    // 二分上界：答案至多是所有数的和（即只分成 1 段）
    ll r = sum;

    // 二分查找
    while (l <= r) {
        ll mid = l + (r - l) / 2;
        if (check(N, M, mid)) {
            // 如果 limit = mid 可行（分的段数 <= M），说明答案可能是 mid
            // 或者更小
            r = mid - 1;
        } else {
            // 如果不可行（分的段数 > M），说明 limit 太小了，需要增大
            l = mid + 1;
        }
    }

    // 最终 l 指向的就是满足条件的最小值
    std::cout << l << '\n';
    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

GESP, 五级

GESP C++ 二分答案贪心

本文由作者按照 CC BY-NC-SA 4.0 进行授权