P1182 数列分段`Section II`题解（博客搬家）

题面

题目描述

对于给定的一个长度为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。

输入

第1行包含两个正整数N，M。 第2行包含N个空格隔开的非负整数Ai，含义如题目所述。

输出

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

样例输入

5 3 4 2 4 5 1

样例输出

6

提示

对于20%的数据，有N≤10； 对于40%的数据，有N≤1000； 对于100%的数据，有N≤100000, M≤N,Ai之和不超过10^9。

题目分析

算法：二分算法

首先，我们要输入。 （废话） 输入中可以确定左指针与右指针的位置。

scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); r+=a[i]; if(a[i]>l) l=a[i]; }

接下来，我们打一个二分的框架。 （不会打的别看了） 我在下面会讲。

while(l<=r){ m=l+(r-l)/2; t=0,tot=0; if(judge(m))l=m+1;//缩小范围 else r=m-1; }

有人会问，函数 $judge$ 里是什么呢？ 我当然会讲（不讲写这题解干嘛） 重点（敲黑板）：

inline bool judge(int x){ for(int i=1;i<=n;i++){ if((t+a[i])<=x) t+=a[i]; else{ t=a[i]; tot++; } } return tot>=k; }

让我们逐步分析！ 第一行就不用解读了吧。 第二行，循环，找到分段的数量。

for(int i=1;i<=n;i++){

接下来，判断。

if((t+a[i])<=x) t+=a[i]; else{ t=a[i]; tot++; }

如果这个段落里还可以塞数据，我们就塞。 如果塞不进去，就将计数器加一，把段落清空，重新塞。 塞完了就判断是否达到段落要求，达到了就返回。

return tot>=k;

最后输出。

code

#include <bits/stdc++.h> using namespace std; int n,k; int l,r,m; long long t,tot,a[10000001]; inline bool judge(int x) { for(int i=1;i<=n;i++) { if((t+a[i])<=x) t+=a[i]; else{ t=a[i]; tot++; } } return tot>=k; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); r+=a[i]; if(a[i]>l) l=a[i]; } while(l<=r) { m=l+(r-l)/2; t=0,tot=0; if(judge(m))l=m+1; else r=m-1; } printf("%d",l); return 0; }

附录：二分框架分析 （这里把变量定得明确一些）

while（left<=right) { mid=left+(right-left)/2;//也可以用(left+right)/2，这里用left+(right-left)/2纯属喜好，都是求中点数值。 if(judge(mid))left=mid+1; else right=mid-1; }

( $left$ 表示左指针，$right$ 表示右指针，中点为 $mid$ ) 我们先取中点，然后判断所要求的数值所在的范围， 如果合法，说明数值可能在中点右边，将左指针移至当前中点。 如果不合法，说明数值可能在中点左边，将右指针移至当前中点。 继续判断直到左指针大于等于右指针，就得出所求答案了。