|
Размер: 3948
Комментарий:
|
← Версия 7 от 2023-01-10 15:15:48 ⇥
Размер: 3950
Комментарий:
|
| Удаления помечены так. | Добавления помечены так. |
| Строка 29: | Строка 29: |
| Обещаный жадный алгоритм: в оптимальном решении штраф `p` за каждое не решённое вовремя задания c дедлайном `d` не должен превосходить возможный штраф каждого задания, решённого ''за период d'' вовремя. Действительно: | Обещанный жадный алгоритм: в оптимальном решении штраф `p` за каждое не решённое вовремя задания c дедлайном `d` не должен превосходить возможный штраф каждого задания, решённого ''за период d'' вовремя. Действительно: |
| Строка 39: | Строка 39: |
| Если поиск свободного дня для `d` линеен, некоторые тесты не пройдут по времени. Можно было хранить вни в двоичном дереве (это быстрее всего), но мне было лень, и я воспользовался [[py3doc:bisect]]. | Если поиск свободного дня для `d` линеен, некоторые тесты не пройдут по времени. Можно было хранить дни в двоичном дереве (это быстрее всего), но мне было лень, и я воспользовался [[py3doc:bisect]]. |
Ввести построчно список пар натуральных чисел, каждое из которых не больше 200000; последняя строка пустая. Каждая пара — это день, до которого включительно должно быть выполнено некоторое задание (нумерация начинается с 1), и штраф за невыполнение задания вовремя. На выполнение одного задания уходит один день, параллельно их выполнить нельзя. Вывести минимально возможный штраф за выполнение всех заданий.
1 2 2 2 1 2 3 1
В первый день можно сделать третье задание, во второй — второе, в третий — четвёртое, а первое придётся делать после дедлайна, получив в сумме штраф 2 балла. Вариантов более одного, но меньше не получится.
- Подсказка 1: несмотря на минимаксную природу задачи, здесь работает один из «жадных» алгоритмов.
- Подсказка 2: квадратичная сложность алгоритма (количество дней × количество заданий) — это слишком много, что-то из этого надо сократить до логарифма
2
Спойлер: