首先通过二分来确定这种最大值最小的问题。
假设每个区间的和的最大值为x，那么只要判断的时候只要贪心即可。
也就是如果和不超过x就一直往区间里放数，否则就开辟一个新的区间，这样来判断是否k个区间容得下这些数。
还有就是输出也挺麻烦的，借鉴了一下lrj的代码，感觉也是十分巧妙。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 500 + 10; 6 LL a[maxn]; 7 bool last[maxn]; 8 int n, k; 9 10 bool check(LL x) 11 { 12 int cnt = 1; 13 for(int i = 0, j; i < n; i = j) 14 { 15 if(cnt > k) return false; 16 LL s = 0; 17 for(j = i; j < n; j++) 18 { 19 if(a[j] > x) return false; 20 if(s + a[j] <= x) s += a[j]; 21 else break; 22 } 23 cnt++; 24 } 25 return true; 26 } 27 28 int main() 29 { 30 //freopen("in.txt", "r", stdin); 31 //freopen("out.txt", "w", stdout); 32 33 int T; scanf("%d", &T); 34 while(T--) 35 { 36 scanf("%d%d", &n, &k); 37 LL L = 0, R = 0; 38 for(int i = 0; i < n; i++) { scanf("%lld", &a[i]); R += a[i]; } 39 while(L < R) 40 { 41 LL mid = (L + R) / 2; 42 if(check(mid)) R = mid; 43 else L = mid + 1; 44 } 45 46 memset(last, false, sizeof(last)); 47 LL s = 0; int r = k; 48 for(int i = n-1; i >= 0; i--) 49 { 50 if(s + a[i] > L || i + 1 < r) 51 { 52 last[i] = true; 53 s = a[i]; 54 r--; 55 } 56 else s += a[i]; 57 } 58 for(int i = 0; i < n-1; i++) 59 { 60 printf("%lld ", a[i]); 61 if(last[i]) printf("/ "); 62 } 63 printf("%lld ", a[n-1]); 64 } 65 66 return 0; 67 }