贪心-数列划分

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;
}