Ввести построчно список пар натуральных чисел, каждое из которых не больше 200000; последняя строка пустая. Каждая пара — это день, до которого включительно должно быть выполнено некоторое задание (нумерация начинается с 1), и штраф за невыполнение задания вовремя. На выполнение одного задания уходит один день, параллельно их выполнить нельзя. Вывести минимально возможный штраф за выполнение всех заданий.
1 2 2 2 1 2 3 1
В первый день можно сделать третье задание, во второй — второе, в третий — четвёртое, а первое придётся делать после дедлайна, получив в сумме штраф 2 балла. Вариантов более одного, но меньше не получится.
- Подсказка 1: несмотря на минимаксную природу задачи, здесь работает один из «жадных» алгоритмов.
- Подсказка 2: квадратичная сложность алгоритма (количество дней × количество заданий) — это слишком много, что-то из этого надо сократить до логарифма
2
Спойлер:
Обещанный жадный алгоритм: в оптимальном решении штраф p за каждое не решённое вовремя задания c дедлайном d не должен превосходить возможный штраф каждого задания, решённого за период d вовремя. Действительно:
Предположим, мы составили график выполнения N - 1 заданий, минимизирующий суммарных штраф. Часть дней di занята выполнением задания со штрафом pi; часть дней свободна
Если ∃ свободный день di ⩽ d, занимаем этот день новым заданием, штраф не меняется
Если ∄ свободного дня di ⩽ d, но штраф p ⩽ pi ∀ i: di ⩽ d
Если ∄ свободного дня di ⩽ d, но можно найти минимальное pk: dk ⩽ d и pk < p
для сохранения минимальности надо в k-й день выполнить новое задание, а k-е задание выполнять невовремя, штраф увеличится на pk (по построению оно минимально)
Лучше сразу отсортировать пары (p, d) по убыванию штрафа и добавлять в график по одной, в свободный день di ⩽ d
Если поиск свободного дня для d линеен, некоторые тесты не пройдут по времени. Можно было хранить дни в двоичном дереве (это быстрее всего), но мне было лень, и я воспользовался bisect.