Линейное разбиение: поделить работу на k кусков подряд

Если ты умеешь записать динамику для линейного разбиения и решить его двоичным поиском по ответу с жадной проверкой, листай до «Теперь сам».

Как думаешь, где резать

Книги одной серии - 3, 1, 4, 1, 5, 9, 2, 6 сантиметров толщиной - надо расставить на три полки, не меняя порядок. Полки покупают по самой длинной. Какой должна быть самая длинная полка?

Прежде чем читать дальше, попробуй очевидное: всего 31 сантиметр, на полку в среднем 10.3. Режь, как только набралось больше среднего. Сколько получится? И почему среднее - это нижняя граница, а не ответ?

На что это похоже

Раздача глав книги трём переводчикам: каждый получает несколько глав подряд, срок сдачи - когда закончит самый медленный. Редактор, режущий «по сто страниц на человека», натыкается на огромную главу, которую резать нельзя, и вся раскладка съезжает. Хороший редактор сначала спрашивает: «а уложимся ли мы в двести страниц на человека?» - и проверить это очень легко: раздавать главы по очереди, пока человек не наберёт двести.

Механизм: динамика и проверка порога

ДИНАМИКА
d[j][i] - наименьший возможный наибольший кусок,
          если первые i элементов разрезаны на j кусков
база:    d[0][0] = 0
переход: последний кусок - a[t..i−1]:
         d[j][i] = min по t ( max( d[j−1][t],  pref[i] − pref[t] ) )
ответ:   d[k][n];  состояний k·n, переход до n - Θ(k·n²)

ПОИСК ПО ОТВЕТУ (все a ≥ 0)
хватит(m): идти слева направо и резать, как только следующий
           элемент сделал бы кусок больше m; кусков ≤ k?
признак монотонен: хватило при m - хватит и при любом большем
двоичный поиск m на [max(a), sum(a)]:  O(n · log sum(a))

Почему жадная проверка верна. При фиксированном пороге m выгодно делать каждый кусок как можно длиннее: если в каком-то решении кусок можно удлинить, не превысив m, следующий от этого только укоротится. Это обменный аргумент: любое решение с не более чем k кусками превращается в жадное, не увеличивая число кусков.

Правило

Линейное разбиение - разрезать последовательность на k отрезков подряд с наименьшим наибольшим отрезком. Динамика по префиксам: d[j][i] = min по t max(d[j−1][t], сумма a[t..i−1]), Θ(k·n²). При неотрицательных элементах быстрее двоичный поиск по ответу: проверка порога m - жадная нарезка самыми длинными кусками, не больше m; монотонность признака даёт O(n · log S). Среднее S/k - нижняя граница, а не ответ.

Разбор: книги на три полки

a = 3 1 4 1 5 9 2 6,  сумма 31,  k = 3

«резать у среднего» (10.3):  3 1 4 1 | 5 | 9 2 6     полки 9, 5, 17
    после второго разреза разрезов не осталось, хвост 17

поиск по ответу, границы [9, 31]:
    хватит(14)?  3 1 4 1 5 =14 | 9 2 =11 | 6     три куска - да
    хватит(13)?  3 1 4 1 =9 | 5 | 9 2 =11 | 6    четыре - нет
    ответ 14:  3 1 4 1 5 | 9 | 2 6   или   3 1 4 1 | 5 9 | 2 6

Наивная нарезка потратила разрез на одинокую пятёрку и оставила хвост в 17. Нижняя граница max(9, 31/3) = 10.3 недостижима: девятка не делится, а соседи у неё такие, что меньше 14 не выходит.

Разбор: пятьсот массивов и сто тысяч элементов

Программа сравнивает динамику с поиском по ответу на пятистах случайных массивах, считает, как часто ошибается «резать у среднего», и решает задачу на ста тысячах элементов, где динамика за k·n² уже не годится.

import itertools
import random


def dinamika(a, k):                   # d[j][i]: первые i элементов
    n = len(a)                        # на j кусков, лучший наибольший
    pref = list(itertools.accumulate(a, initial=0))
    INF = float("inf")
    d = [[INF] * (n + 1) for _ in range(k + 1)]
    d[0][0] = 0
    for j in range(1, k + 1):
        for i in range(1, n + 1):
            for t in range(j - 1, i):     # последний кусок a[t..i−1]
                c = max(d[j - 1][t], pref[i] - pref[t])
                d[j][i] = min(d[j][i], c)
    return d[k][n]


def po_otvetu(a, k):                  # двоичный поиск по ответу
    def hvatit(m):                    # жадно: резать, когда кусок > m
        kuskov, s = 1, 0
        for x in a:
            if s + x > m:
                kuskov, s = kuskov + 1, 0
            s += x
        return kuskov <= k
    lo, hi = max(a), sum(a)
    while lo < hi:
        m = (lo + hi) // 2
        if hvatit(m):
            hi = m
        else:
            lo = m + 1
    return lo


def po_srednemu(a, k):                # «резать у среднего» - наивно
    cel, s, kuski, tek = sum(a) / k, 0, [], 0
    for x in a:
        if tek + x > cel and len(kuski) < k - 1 and tek > 0:
            kuski.append(tek)
            tek = 0
        tek += x
    return max(kuski + [tek])


rng = random.Random(26)
huzhe = 0
for _ in range(500):
    a = [rng.randint(1, 50) for _ in range(rng.randint(5, 30))]
    k = rng.randint(2, 5)
    d = dinamika(a, k)
    assert d == po_otvetu(a, k)
    huzhe += po_srednemu(a, k) > d
print("500 массивов: динамика и поиск по ответу совпали всегда")
print("«резать у среднего» хуже оптимума в", huzhe, "случаях")
a = [rng.randint(1, 10 ** 6) for _ in range(10 ** 5)]
print("100 000 элементов на 8 кусков:", po_otvetu(a, 8))
print("нижняя граница sum/k:", sum(a) // 8)

500 массивов: динамика и поиск по ответу совпали всегда
«резать у среднего» хуже оптимума в 383 случаях
100 000 элементов на 8 кусков: 6258082014
нижняя граница sum/k: 6257749680

Два точных метода совпали везде. «Резать у среднего» промахнулось в 383 случаях из 500. На ста тысячах элементов поиск по ответу сделал около тридцати шести проверок по 10⁵ шагов; динамика потребовала бы 8 · 10¹⁰ действий. Ответ на большом массиве лишь на 0.005% выше нижней границы sum/k: когда элементов много и они мелкие относительно суммы, разбиение почти идеально.

Что ломается без этого

Первая ошибка - решать жадно «по среднему» и не проверять: ответ правдоподобен и часто неверен. Вторая - применять поиск по ответу к массивам с отрицательными числами: признак «хватит ли k кусков» перестаёт быть монотонным, а жадная нарезка - верной; остаётся динамика. Третья - перепутать задачу с разбиением на два РАВНЫХ по сумме множества без сохранения порядка: это уже сумма подмножеств, и она трудна. Четвёртая - начать двоичный поиск с нуля, а не с наибольшего элемента: при m меньше элемента жадная нарезка зацикливается или врёт.

Зачем это в работе

Распределение последовательной работы: страницы по принтерам, кадры видео по машинам рендера, строки таблицы по потокам, главы по переводчикам, участки трубы по бригадам. Везде, где куски обязаны идти подряд и срок определяет самый загруженный. Отдельная польза приёма «поиск по ответу + жадная проверка» - он работает для десятков задач вида «минимизировать наибольшее»: при фиксированном пороге проверка часто тривиальна, даже когда прямая оптимизация трудна.

Теперь сам

a = 7 2 5 10 8, k = 2. Найди ответ поиском по ответу: какие пороги проверяет двоичный поиск и где режет жадная проверка на ответе?