Что спрашивают
Заявка задаёт начало участка и его длину на дороге длиной 10 000. Пересекающиеся участки несовместимы, но конец одного может совпадать с началом другого.
Нужно выполнить максимум заявок и при этом минимизировать неубранный хвост в конце дороги. N ≤ 2000, начала и длины натуральные, все участки внутри дороги. Выведите количество и длину хвоста.
Приём решения
Обычный выбор по самому раннему окончанию максимизирует количество, но сам по себе не решает второй критерий: последнюю заявку иногда выгодно заменить более длинной. Используем динамику, которая рассматривает каждый возможный последний участок.
Преобразуем пары в (end = start + length, start) и отсортируем по end. Массив prefix[j] хранит максимум совместимых заявок среди первых j участков. Для текущего участка найдём j — число уже просмотренных концов, не больших его начала. Это bisect_right(ends, start, 0, i).
Если завершить выбор текущим участком, получится count = prefix[j] + 1. В новый элемент prefix запишем максимум старого значения и count. Отдельно сравним пару (count, end) с лучшей: больший конец при том же количестве уменьшает хвост.
Каждая допустимая последовательность имеет последнюю заявку, и для неё рассмотрен лучший предшествующий набор. Поэтому максимум по всем последним заявкам даёт оба критерия. Время O(N log N), память O(N).
Разбор на примере
Ввод
5 8 30 1 3 2 15 8 2 4 4
Вывод
3 9962
| Текущий участок | Лучший набор с ним последним | Лучшее количество в префиксе |
|---|---|---|
| [1; 4] | 1 | 1 |
| [4; 8] | 2 | 2 |
| [8; 10] | 3 | 3 |
| [2; 17] | 1 | 3 |
| [8; 38] | 3; конец дальше | 3 |
Участки [1; 4] и [4; 8] совместимы. После них можно выполнить [8; 10] или [8; 38]. Оба способа дают три заявки, но второй оставляет хвост 10 000 - 38 = 9962. Участок [2; 17] перекрывает первые два и не улучшает количество.
Код на Python и C++
Число j одновременно является индексом prefix: первые j концов совместимы с текущим началом. bisect_right включает равные границе концы.
В C++ вместо bisect_right — upper_bound(ends.begin(), ends.begin() + i, start) - ends.begin(): он даёт то же j.
from bisect import bisect_right
import sys
def solve(requests):
intervals = sorted((start + length, start) for start, length in requests)
ends = [end for end, start in intervals]
prefix = [0]
best = (0, 0)
for i, (end, start) in enumerate(intervals):
j = bisect_right(ends, start, 0, i)
count = prefix[j] + 1
prefix.append(max(prefix[-1], count))
best = max(best, (count, end))
return best[0], 10000 - best[1]
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
requests = list(zip(data[1::2], data[2::2]))
print(*solve(requests))
<algorithm>
<iostream>
<utility>
<vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> intervals(n);
for (auto& [end, start] : intervals) {
int length;
cin >> start >> length;
end = start + length;
}
sort(intervals.begin(), intervals.end());
vector<int> ends(n);
for (int i = 0; i < n; i++)
ends[i] = intervals[i].first;
vector<int> prefix = {0};
pair<int, int> best = {0, 0};
for (int i = 0; i < n; i++) {
auto [end, start] = intervals[i];
int j = upper_bound(ends.begin(), ends.begin() + i, start) - ends.begin();
int count = prefix[j] + 1;
prefix.push_back(max(prefix.back(), count));
best = max(best, {count, end});
}
cout << best.first << ' ' << 10000 - best.second << endl;
}
Типичные ошибки
- Принять длину за координату конца
Второе число входной строки — длина. Координату конца нужно вычислить как start + length.
- Запретить касание границ
Участки с концом, равным началу следующего, совместимы. Нужен bisect_right, а не исключение равенства.
- Вывести хвост первого жадного набора
Самый ранний конец помогает количеству, но среди наборов максимального размера нужен самый поздний последний конец.