意甲冠军：k手稿的部分成m部分，使每一个和最小

思路：典型最大值最小化问题，使用贪心+二分。

贪心的是每次尽量将元素往右边划分，二分查找最小的x满足m个连续的子序列和S(i)都不超过x。

由于输出的原因。在划分时就从后往前尽量划分。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1005;

int m, k, t;

int arr[MAXN], vis[MAXN];

ll ans, sum, Min;

int judge(ll x) {

    memset(vis, 0, sizeof(vis));

    ll s = 0;

    t = 0;

    int flag = 1;

    for (int i = m - 1; i >= 0; i--) {

        if (arr[i] > x) {

            flag = 0;

            break;

        }

        if (s + arr[i] > x) {

            vis[i] = 1;

            t++;

            s = arr[i];

            if (t > k - 1) {

                flag = 0;

                break;

            }

        }

        else

            s += arr[i];

    }

    return flag;

}

int binary() {

    ll x = Min, y = sum;

    while (x < y) {

        ll mid = x + (y - x) / 2;

        if (judge(mid))

            y = mid;

        else

            x = mid + 1;

    }

    return x;

}

void outPut() {

    judge(ans);

    int num = k - 1 - t;

    for (int i = 0; i < m; i++) {

        if (vis[i] == 0 && num) {

            vis[i] = 1;

            num--;

        }

    }

    for (int i = 0; i < m - 1; i++) {

        printf("%d ", arr[i]);

        if (vis[i])

             printf("/ ");

    }

    printf("%d\n", arr[m - 1]);

}

int main() {

    int cas;

    scanf("%d", &cas);

    while (cas--) {

        scanf("%d %d", &m, &k);

        ans = 0;

        Min = arr[0];

        for (int i = 0; i < m; i++) {

            scanf("%d", &arr[i]);

            sum += arr[i];

            if (Min < arr[i])

                Min = arr[i];

        }

        ans = binary();

        outPut();

    }

    return 0;

}