C++14(g++5.4) 解法, 执行用时: 21ms, 内存消耗: 860K, 提交时间: 2020-05-10 14:12:55

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int n,m,l,r;
int a[100010];
bool chk(int x){
	int now=1;
	rep(i,1,m){
		int sum=a[now],mx=a[now];
		while(sum-mx<=x&&now<=n){
			now++;
			sum+=a[now];
			mx=max(mx,a[now]);
		}
	}
	return (now==n+1);
}
int main(){
	cin>>n>>m;
	rep(i,1,n)	scanf("%d",a+i);
	l=-1;r=1e9+7;
	while(r-l>1){
		int mid=(r+l)/2;
		if(chk(mid)){
			r=mid;
		}	
		else{
			l=mid;	
		}
	}
	printf("%d\n",r);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 28ms, 内存消耗: 984K, 提交时间: 2020-05-10 15:39:10

#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[1000005];
int check(int mid)
{
	int mx=0,cnt=1,sum=0;
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,t[i]);
		if(sum+t[i]-mx<=mid) sum+=t[i];
		else
		{
			cnt++;
			mx=t[i];
			sum=t[i];
		}
	}
	if(cnt<=m) return 1;
	else return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	int l=0,r=1e9+5,mid;
	while(l<r)
	{
		mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}