首页 > 代码库 > 1182 数列分段2
1182 数列分段2
难度：普及/提高-
题目类型：二分
提交次数：2
涉及知识：二分/贪心
题目描述
对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤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。
输入输出格式
输入格式：
输入文件divide_b.in的第1行包含两个正整数N，M，第2行包含N个空格隔开的非负整数A[i]，含义如题目所述。
输出格式：
输出文件divide_b.out仅包含一个正整数，即每段和最大值最小为多少。
代码：
1 #include<iostream> 2 using namespace std; 3 int a[100010]; 4 int n, m; 5 bool check(int maxx){ 6 int sum = 0, tot = 1; 7 for(int i = 0; i < n; i++){ 8 if(sum+a[i]<=maxx) sum+=a[i]; 9 else{10 sum = a[i]; tot++;11 }12 }13 if(tot>m) return false;14 return true;15 }16 int main(){17 cin>>n>>m;18 int i;19 int maxx = 0;20 int sum = 0;21 for(i = 0; i < n; i++){22 cin>>a[i];23 maxx = max(maxx, a[i]);24 sum += a[i];25 }26 int l = maxx, r = sum;27 int ans;28 while(l <= r){29 int mid = (l+r)/2;30 if(check(mid)){31 r = mid-1;32 ans = mid;33 }34 else l = mid+1;35 }36 cout<<ans;37 return 0;38 }
备注：
最值问题首先考虑二分！！！！
比较标准的二分+贪心，和跳石头很像。注意是l<=r，否则l==r的时候就不会再check了。。还有，tot初始化为1.。
其实我不是很理解在给定答案进行验证的时候的贪心选择策略。为什么要让一组的和尽可能大？直觉应该是这样的，但细想又没有根据。再跟老师讨论吧qwq。
1182 数列分段2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。