C++14(g++5.4) 解法, 执行用时: 65ms, 内存消耗: 1304K, 提交时间: 2019-10-23 15:46:15

#include<bits/stdc++.h>
using namespace std;

int main() {
  int N, M; cin >> N >> M;
  vector<int> A(N); for (auto &a: A) cin >> a;
  int lo = *max_element(A.begin(), A.end());
  int hi = accumulate(A.begin(), A.end(), 0ll) + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int cnt = 1;
    int cur = 0;
    for (auto a: A) {
      if (cur + a > mid) cnt++, cur = 0;
      cur += a;
    }
    if (cnt > M) lo = mid + 1;
    else hi = mid;
  }
  cout << hi << endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 22ms, 内存消耗: 792K, 提交时间: 2022-09-06 11:46:50

#include<cstdio>
const int M=1e5+10;
int a[M],n,m;
bool check(int mid)
{
	int t=1,d=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>mid)return 0;
		if(d+a[i]<=mid)d+=a[i];
		else t++,d=a[i];
	}
	return t<=m;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int l=1,r=1e9,ans=0;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1; 
	}
	printf("%d",ans);
	return 0;
}