本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674729.html

题目链接

题目

对于给定的一个长度为N的正整数数列 A1∼NA_{1\sim N}，现要将其分成 MM（M≤NM\leq 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。

思路

二分最小值，然后我们对于每次二分的值进行判断，于是就转换为：

给出一个序列，每段和的最大值不得超过 midmid，问最多能分出多少段。

如果段数超过 kk，说明可行。

时间复杂度 O(nlog⁡n)O(n\log n)

由于这道题是我2021.8做的，所以那时码风很现在的不太一样。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m,i,j,k;
int a[1000010];
int sum,now,t;
int l,r,mid;

int pan(int x)
{
	now=0;
	t=1;
	for(i=1;i<=n;++i)
	{
		if(a[i]>x)
			return 0;
		if(now+a[i]>x)
		{
			now=a[i];
			++t;
			if(t>m)
				return 0;
		}
		else
			now+=a[i];
	}
	return 1;
}

signed main()
{
//	freopen("seqseg.in","r",stdin);
//	freopen("seqseg.out","w",stdout);
//	std::ios::sync_with_stdio(false);
	n=read();
	m=read();
	for(i=1;i<=n;++i)
		a[i]=read(),sum+=a[i];
	l=0,r=sum;
	while(l<=r)
	{
		mid=l+r>>1;
		if(pan(mid))
			r=mid-1;
		else
			l=mid+1;
	}
//	for(int i=1;i<=sum;++i)
//		printf("%d: %d\n",i,pan(i));
	printf("%d",l);
	return 0;
}