邓俊辉算法训练营 -- 分组

描述

有n个正整数排成一排，你要将这些数分成m份（同一份中的数字都是连续的，不能隔开），同时数字之和最大的那一份的数字之和尽量小。

输入

输入的第一行包含两个正整数n，m。

接下来一行包含n个正整数。

输出

输出一个数，表示最优方案中，数字之和最大的那一份的数字之和。

样例

样例输入

5 2
2 1 2 2 3

样例输出

5

样例解释

若分成2和1、2、2、3，则最大的那一份是1+2+2+3=8；

若分成2、1和2、2、3，则最大的那一份是2+2+3=7；

若分成2、1、2和2、3，则最大的那一份是2+1+3或者是2+3，都是5；

若分成2、1、2、2和3，则最大的那一份是2+1+2+2=7。

所以最优方案是第三种，答案为5。

提示

• 大家记得看到“最大的最小”这一类语言，一定要想二分能不能做。
• 我们二分最大的那一份的和d，然后从左向右分组，在一组中，在和不超过d的情况下尽量往右分。若最终分出来的组数小于等于m，则这显然是合法的（我们在分出来的组里随便找个地方切开，总能变到m组，且每组的和不超过d）
• 这个d显然是单调的，即，若和不超过d能分成m组，则和不超过d+1也是能分成m组的，故二分正确。

Python 3代码实现（OJ通过100分）

#!/usr/bin/env pypy3
# -*- coding: UTF-8 -*-

# ================= 代码实现开始 =================

def check(d, n, m, a):
    sum = 0
    cnt = 1
    i = 0
    while (i < n):
        if a[i] > d:
            return False
        sum += a[i]
        i += 1
        if (sum > d):
            cnt += 1
            i -= 1
            sum = 0

    if (cnt > m):
        return False
    else:
        return True

# 将所给数组分成连续的m份，使得数字之和最大的那一份的数字之和最小
# n：数组大小
# m：题中的m
# a：所给数组，大小为n
# 返回值：最优方案中，数字之和最大的那一份的数字之和

def getAnswer(n, m, a):
    r = 0
    l = 1

    for i in range(n):
        r += a[i]

    while (l <= r):
        mid = (l + r) // 2 #这一步是分而治之的思想
        if (check(mid, n, m, a)):
            r = mid - 1
        else:
            l = mid + 1

    return (r + 1)

# ================= 代码实现结束 =================
if __name__ == "__main__":
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    print(getAnswer(n, m, a))