Description
给一个有 n 个正整数的序列，连续地将其分为互不重叠的 k 份，即每一份都是该序列的一个子串，不能调换顺序。
求一个划分方案，使数字之和最大的那一份，其和在所有方案里最小。
Input
每组数据第一行两个整数 n, k，其中1 ≤ k ≤ n ≤ 105。
第二行 n 个不大于 1000 的正整数。
Output
求划分 k 份让数字之和最大那一份的和最小的方案，在划分位置标注 “/”，与数字用空格隔开。
如果有多种方案，输出第一个块最小的方案，如果依然多种，则第二个块最小，依此类推。
Sample Input
9 3
10 20 30 40 50 60 70 80 90
Sample Output
10 20 30 40 50 / 60 70 / 80 90
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<cmath>
#include<complex>
#include<vector>
#include<algorithm>
const int maxn = 1e5 + 10;
int n, k, a[maxn];
bool split[maxn];
bool Judge(int mid)
{
int cnt = 1, tmpsum = 0;
for(int i = 0; i < n; i ++)
{
if(a[i] > mid) return false;
if(tmpsum + a[i] > mid)
tmpsum = 0, cnt ++;
tmpsum += a[i];
if(cnt > k) return false;
}
return true;
}
int main()
{
while(scanf("%d%d", &n, &k) != EOF)
{
for(int i = 0; i < n; i ++)
scanf("%d", &a[i]);
int left = 0, right = 1e9, mid;
while(left < right)
{
mid = left + right >> 1;
if(Judge(mid)) right = mid;
else left = mid + 1;
}
int tmpsum = 0, cnt = 0;
memset(split, 0, sizeof(split));
for(int i = n - 1; i >= 0; i --)
{
if(tmpsum + a[i] > left || i + 1 < k - cnt)
tmpsum = 0, split[i] = true, cnt ++;
tmpsum += a[i];
}
for(int i = 0; i < n; i ++)
{
printf(" %d" + !i, a[i]);
if(split[i]) printf(" /");
}
printf("\n");
}
return 0;
}
