【二分答案 C/C++】洛谷P1182 数列分段 Section II

2025 - 03 - 02 - 第 66 篇
Author: 郑龙浩 / 仟濹
【二分搜索/二分答案】

洛谷P1182 数列分段 Section II

题目描述

对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\le N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $42451$ 要分成 $3$ 段。

将其如下分段：

$$[42][45][1]$$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$$[4][24][51]$$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $42451$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。

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

输出格式

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

输入输出样例 #1

输入 #1

5 3
4 2 4 5 1

输出 #1

6

说明/提示

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

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

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

思路

看到本题，首先想到求的是最大值的最小化–>使用二分答案

解题核心：二分法寻找最小化段和最大值

1 每段和的最大值最小 什么意思？？

这句话有点绕，我想了一阵子才明白什么意思，可能是我理解能力有限吧

意思其实很简单， 就是

• 存在多种分法，每种分法会将数组分成多个段
• 计算各段的和。在每种分法中，至少存在一段，其和为该分法中最大的和。

2 大体思路

变量

M - 分段数量
num - 数字数量
arr - 数组vector
count - 实际分段数量
sum - 记录每一段的和
left - 左边界
right - 右边界
mid - 边界的中间值(待定答案)

1. 范围（每段和的最大值的最小值）

   所有数中的最大值~所有数的和

   • 所有数中的最大值 - 最极端的一种情况就是分了好多段，但是就是有那么一段只有一个数字，这个数字还是这些段中最大的
   • 所有数的和 - 最极端的另一种情况就是所有数字就分一段，那么最大值也只能是这一段的和了

   注意，这个操作如果输入以后再单独运算又要循环，所以在输入的同时直接计算出 所有数中的最大值，所有数的和即可。

   left, right
   

2. 使用二分答案去求解

   注意：刚开始段数就是1，就算是不分段，也是只有一段，默认cnt = 1

   • 范围 所有数中的最大值~所有数的和

   • check函数 - check( mid )

     sum每次对符合条件的元素累加，如果本次元素 + sum <= mid，表示没有达到或刚好等于设限的每段的和，可以继续加；如果本次元素 + sum > mid，则超过设限每段的和。

     此时，分段数量要加一cnt ++，且新开一段，重新开始累加

     最后：

     段数<=设限段数 - 返回 1
     段数> 设限段数 - 返回 0

   2. 判断 check(mid)

   若 == 1，则表示段数 <= 设限段数，符合段数要求，可以尝试 更小的限制(更小的每段和最大值最小)，使段数增多

   此时，应该将 右边界调小，right = mid - 1

   若 == 0，则表示段数 > 设限段数，段数太多，必须要尝试 更大的限制(更大的每段和最大值最小)，使段数减少，

   此时，应该将 左边界调大，left = mid + 1

   3. 最终确定下来 mid，打印即可

代码

// 洛谷P1182数列分段
// 2025-03-02
// 郑龙浩/仟濹
// 解题核心：二分法寻找最小化段和最大值
// M - 分段数量
// num - 数字数量
// arr - 数组vector
// ans - 存储答案
// count - 实际分段数量
// sum - 记录每一段的和
// left - 左边界
// right - 右边界


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int M, num; // 分段数量，数字数量
vector <int> arr; // 所有数字
// 变量
bool check( int mid ){
    int cnt = 1; // 当前分段数量（至少需要1段），即使没分，也是只有一段
    int sum = 0; // 记录每一段的和
    for (int i = 0; i < num; i++){
        if( arr[ i ] > mid ) return false;
        // 总和没有超过设限之和
        if( arr[ i ] + sum <= mid ){
            sum += arr[ i ];
        } else { // 总和超过设限之和 arr[ i ] + sum > mid 
            sum = arr[ i ]; // 更新 sum，使其变为下一段的第一个数字，然后进入下一次循环，继续如上操作
            cnt ++;
        }
    }
//   >**段数<=设限段数 - 返回 1**
//   >**段数>  设限段数 - 返回 0**
    return cnt <= M;
}
int main( void ){
    cin >> num >> M; // 输入处理：注意N对应变量num（数列长度），M是目标分段数
    arr.resize(num); // 设置vector宽度
    int left = 0, right = 0; // 左右边界，初始左边界应为数组最大值，右边界为全部元素之和
    int mid; // 中间值(待定答案)
    int ans = 0; // 存储答案
    for( int i = 0; i < num; i ++ ){
        cin >> arr[ i ];
        if( left < arr[ i ] ) left = arr[ i ]; // 找出最大的数字，使左边界为最大值
        right += arr[ i ]; // 计算出所有数字之和，使有边界为所有数字之和
    }
    while ( left <= right ){
        mid = ( left + right ) / 2; // 中间值(待定答案)
        // 段数 <= M，表示课符合段数要求，可以尝试 更小的限制(更小的每段和最大值最小)**，使**段数增多**，
        // 此时，应该将 **右边界调小**，`right = mid - 1`
        if (check( mid )){ 
            ans = mid;
            right = mid - 1;
        }
        // 若 `== 0`，则表示**段数 > 设限段数**，段数太多，必须要尝试 **更大的限制(更大的每段和最大值最小)**，使**段数减少**，
        // 此时，应该将 **左边界调大**，`left = mid + 1` 
        else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}