本题考虑使用二分答案。

思路

关于本题单调性的证明：因为显示器的宽度越大，一行能显示的宽度越多，所以显示需要的行数越少（单词总量不变）。所以显示器的宽度和显示需要的行数具有单调递减的关系，所以可以使用二分。

二分枚举显示器的宽度 $w$，然后计算以 $w$ 为宽度显示单词需要的最少行数，如果需要的行数小于等于 $m$，则符合要求，否则不符合要求。

怎么计算呢？

如果显示器的宽度 $w$ 小于单词的最大宽度 $mw$，说明一个单词都无法放进显示器中，显然是不符合要求的。

令 $sum$ 表示当前行已经用了多少宽度，$cnt$ 表示当前用了多少行，一次枚举单词的长度 $l_i$，如果当前宽度加上一个空格和 $l_i$ 的长度大于 $w$，说明当前行已经放不下这个单词了，需要新开一行，让 $cnt$ 加 $1$，并且让 $sum$ 等于 $l_i$，否则 $sum$ 加上 $l_i$ 和一个空格的长度。

时间复杂度：二分的复杂度是 $O(\log n)$，计算一遍的复杂度是 $O(n)$，整体时间复杂度 $O(n \log n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long
using namespace std;
int l[1000010],n,m,p,mw;
bool check(int w){
    if(w<mw)return 0;
	int cnt=1,sum=0;
	sum=l[1];
	for(int i=2;i<=n;i++){
		if(sum+l[i]+1>w)sum=l[i],cnt++;
		else sum+=l[i]+1;
	}
	return cnt<=m;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>l[i],mw=max(mw,l[i]);
	for(int i=(1LL<<62);i;i>>=1)if(!check(p+i))p+=i;
	cout<<p+1LL<<endl;
	return 0;
}