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

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

文章目录 洛谷P1182 数列分段 Section II题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 说明/提示思路1 每段和的最大值最小 什么意思？？2 大体思路代码

洛谷P1182 数列分段 Section II 题目描述

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

关于最大值最小：

例如一数列 4   2   4   5   1 4\ 2\ 4\ 5\ 1 4 2 4 5 1 要分成 3 3 3 段。

将其如下分段：

[ 4   2 ] [ 4   5 ] [ 1 ] [4\ 2][4\ 5][1] [4 2][4 5][1]

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

将其如下分段：

[ 4 ] [ 2   4 ] [ 5   1 ] [4][2\ 4][5\ 1] [4][2 4][5 1]

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

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

所以可以得到要将数列 4   2   4   5   1 4\ 2\ 4\ 5\ 1 4 2 4 5 1 要分成 3 3 3 段，每段和的最大值最小为 6 6 6。

输入格式

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

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

输出格式

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

输入输出样例 #1 输入 #1 5 3 4 2 4 5 1 输出 #1 6 说明/提示

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

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

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1≤N≤105， M ≤ N M\leq N M≤N， A i < 1 0 8 A_i < 10^8 Ai​<108， 答案不超过 1 0 9 10^9 109。

思路

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

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

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

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

意思其实很简单， 就是

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

变量

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

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

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

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

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

left, right

使用二分答案去求解

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

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

check函数 - check( mid )

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

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

最后：

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

判断 check(mid)

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

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

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

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

最终确定下来 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; }