本文主要是介绍洛谷P1182数列分段，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
对于给定的一个长度为 N 的正整数数列 ，现要将其分成 M（M≤N）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 4 2 4 5 14 2 4 5 1 要分成 33 段。
将其如下分段：
[4 2][4 5][1][4 2][4 5][1]
第一段和为 66，第 22 段和为 99，第 33 段和为 11，和最大值为 99。
将其如下分段：
[4][2 4][5 1][4][2 4][5 1]
第一段和为 44，第 22 段和为 66，第 33 段和为 66，和最大值为 66。
并且无论如何分段，最大值不会小于 66。
所以可以得到要将数列 4 2 4 5 14 2 4 5 1 要分成 33 段，每段和的最大值最小为 66。
输入格式
第 11 行包含两个正整数 N,M。
第 22 行包含 N 个空格隔开的非负整数 Ai，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
输入输出样例
输入 #1
5 3 4 2 4 5 1
输出 #1
6
说明/提示
对于 20%20% 的数据，N≤10。
对于 40%40% 的数据，N≤1000。
对于 100%100% 的数据，1≤N≤105，M≤N，Ai<， 答案不超过
。
这道题有了之前的经验，就能看出用二分答案比较合适。
对于二分答案，我想谈谈自己的理解。所谓二分答案，就是“二分”和“答案”两部分，答案是对象，二分是手段，采用二分的手法对答案进行高级枚举。而二分就可以作为一种能够有效降低时间复杂度的一种枚举方法。而二分答案的难点并非二分的函数，而是验证二分出来的mid能不能符合题意的函数，我一般命名为check函数。对于这道题，我想主要讲一下写check函数的具体思路。
关于check函数，具体思路如下（建议配合代码食用）：
1.对于check函数，我要传什么参？我们最终输出的答案是最大值的最小，所以二分答案是对这些值的二分，左限定为0，右限定为输入所有数的和+1，传给check函数就是每次二分后的结果，即（l+r）/2，在check函数中我们定义为x。
2.首先我定义了两个函数，一个now，一个cnt，now的值是当前遍历数组的下标，cnt是将数组分的段数，最终判断x值是否符合条件也是根据cnt判断的。
3.整体思路就是，用now指针从零开始遍历数组，用sum记录每一段的总和，保证不超过m，一旦超过，break跳出循环，继续下次遍历，每次对分段时cnt++，在整个过程中，一旦cnt>m,reruen false;
bool check(int x){int now=0,cnt=0;while(now<n){int sum=0;now++;sum+=num[now];if(sum>x)return false;//如果第一个值就已经大于约定的值x了，那么这个值是注定不可以的，直接return掉就好了while(sum<x&&now<n){//保证每段之和小于m的同时now指针不越界now++;if(sum+num[now]<=x)sum+=num[now];//先试探一下，看看加上下一个元素会不会超过约定值，如果不超过sum直接加上，继续下次循环，如果超过了，记得把now归位，并且跳出循环else {now--;break;}if(sum==x)break;//如果sum刚好等于x了，也break}cnt++;//每一个小循环注定要多一段if(cnt>m)return false;}if(cnt<=m)return true;return false;
}（代码不太美观）
整体代码如下：
//数列分段
#include "iostream"
using namespace std;
int n,m,all;
int num[100005];
bool check(int x){int now=0,cnt=0;while(now<n){int sum=0;now++;sum+=num[now];if(sum>x)return false;while(sum<x&&now<n){now++;if(sum+num[now]<=x)sum+=num[now];else {now--;break;}if(sum==x)break;}cnt++;if(cnt>m)return false;}if(cnt<=m)return true;return false;
}
int binary(){int l=0,r=all+1;while(l+1<r){int mid=(l+r)>>1;if(check(mid))r=mid;else l=mid;}return r;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>num[i];all+=num[i];}int ans=binary();cout<<ans;
}这篇关于洛谷P1182数列分段的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
