csp信奥赛C++高频考点专项训练之贪心算法 --【贪心与二分判定】：数列分段 Section II

csp信奥赛C++高频考点专项训练之贪心算法 --【贪心与二分判定】：数列分段 Section II

题目描述

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

关于最大值最小：

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

将其如下分段：

[ 4 2 ] [ 4 5 ] [ 1 ] [4\ 2][4\ 5][1][42][45][1]

第一段和为6 66，第2 22段和为9 99，第3 33段和为1 11，和最大值为9 99。

将其如下分段：

[ 4 ] [ 2 4 ] [ 5 1 ] [4][2\ 4][5\ 1][4][24][51]

第一段和为4 44，第2 22段和为6 66，第3 33段和为6 66，和最大值为6 66。

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

5 3 4 2 4 5 1

输出 #1

6

说明/提示

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

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

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

思路分析

本题要求将长度为N NN的正整数数列分成连续的M MM段，使得各段和的最大值最小。这是一个典型的“最大值最小化”问题，通常使用二分答案+贪心判断解决。

二分答案

• 假设我们猜测一个值x，表示当前允许的最大段和。
• 如果能用不超过M MM段实现每段和都 ≤x，则 x 可行（可能还可以更小）。
• 否则 `x$ 太小，需要增大。

贪心判断（可行性函数chk(x)）

• 从左到右遍历数列，维护当前段的和s。
• 如果s + a[i] > x，说明a[i]不能放入当前段，必须新开一段（段数c++，s = a[i]）。
• 否则s += a[i]。
• 遍历完成后，若c ≤ M，则 `x$ 可行。

二分边界

• 下界l：数列中的最大值max(A)（因为每段至少包含一个数，段和不可能小于单个最大值）。
• 上界r：题目保证答案不超过10 9 10^9109，因此直接取10 9 10^9109作为上界，无需计算总和。
• 答案在[l, 1e9]内，使用二分查找最小的可行值。

复杂度

• 判断函数chk为O ( N ) O(N)O(N)。
• 二分次数约为log ⁡ 2 ( 10 9 ) ≈ 30 \log_2(10^9) \approx 30log2​(109)≈30，总时间复杂度O ( 30 N ) O(30N)O(30N)，空间复杂度O ( N ) O(N)O(N)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,m,a[100010];//n数列长度,m目标段数,a数列boolchk(intx){//判断最大段和x是否可行intc=1;//当前段数(至少1段)ints=0;//当前段的和for(inti=1;i<=n;++i){if(s+a[i]>x){//加上a[i]会超过限制,则新开一段++c;//段数加1s=a[i];//新段从a[i]开始}else{s+=a[i];//继续累加}}returnc<=m;//段数不超过m则可行}intmain(){scanf("%d%d",&n,&m);intl=0,r=1000000000;//l下界(最大值),r上界(题目保证答案≤1e9)for(inti=1;i<=n;++i){scanf("%d",&a[i]);if(a[i]>l)l=a[i];//更新下界为最大值}intans=r;//初始化答案为上界while(l<=r){//二分查找最小可行值intmid=l+(r-l)/2;//中间值,防止溢出if(chk(mid)){//mid可行ans=mid;//记录答案r=mid-1;//尝试更小值}else{l=mid+1;//不可行,增大下界}}printf("%d\n",ans);return0;}

功能分析

• 输入处理：读取N , M N,MN,M和数列A AA，同时计算二分下界max(A)，上界直接设为10 9 10^9109（题目保证答案在此范围内）。
• 二分搜索：在[maxA, 1e9]范围内二分查找，每次取中点mid并调用chk(mid)判断可行性。当可行时记录ans=mid并缩小右边界；不可行时增大左边界。循环条件为l <= r，确保所有可能值都被检查。
• 贪心判断：chk模拟分段过程，若当前段和加上下一个数会超过mid，则必须新开一段；否则继续累加。最后比较实际段数与M MM。
• 输出结果：最终ans即为最小的最大段和，输出即可。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}