首先通过二分来确定这种最大值最小的问题。
假设每个区间的和的最大值为x，那么只要判断的时候只要贪心即可。
也就是如果和不超过x就一直往区间里放数，否则就开辟一个新的区间，这样来判断是否k个区间容得下这些数。
还有就是输出也挺麻烦的，借鉴了一下lrj的代码，感觉也是十分巧妙。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = + ;
LL a[maxn];
bool last[maxn];
int n, k; bool check(LL x)
{
int cnt = ;
for(int i = , j; i < n; i = j)
{
if(cnt > k) return false;
LL s = ;
for(j = i; j < n; j++)
{
if(a[j] > x) return false;
if(s + a[j] <= x) s += a[j];
else break;
}
cnt++;
}
return true;
} int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout); int T; scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
LL L = , R = ;
for(int i = ; i < n; i++) { scanf("%lld", &a[i]); R += a[i]; }
while(L < R)
{
LL mid = (L + R) / ;
if(check(mid)) R = mid;
else L = mid + ;
} memset(last, false, sizeof(last));
LL s = ; int r = k;
for(int i = n-; i >= ; i--)
{
if(s + a[i] > L || i + < r)
{
last[i] = true;
s = a[i];
r--;
}
else s += a[i];
}
for(int i = ; i < n-; i++)
{
printf("%lld ", a[i]);
if(last[i]) printf("/ ");
}
printf("%lld\n", a[n-]);
} return ;
}
代码君