Что спрашивают
У продукта два срока. Все 2N сроков просматривают по возрастанию. При первом появлении продукта его ставят на первое свободное место с начала, если это срок хранения, или с конца, если это срок после вскрытия. Повторное появление пропускают.
Найдите номер последнего размещённого продукта и число продуктов ниже него. N ≤ 1000, сроки ≤ 10^9, все 2N значений различны. Номера продуктов задаёт исходный порядок строк.
Приём решения
Создадим два события для каждого продукта: (срок, сторона, индекс), где сторона 0 означает начало рейтинга, 1 — конец. Отсортируем события по сроку. Массив used отметит продукты, которые уже получили место.
Свободные позиции всегда составляют сплошной отрезок: размещение забирает только левый или правый край. Поэтому весь рейтинг хранить не требуется, достаточно указателей left и right. Для события неиспользованного продукта занимаем нужный край, двигаем соответствующий указатель и запоминаем номер и позицию.
Последнее успешное размещение определяет ответ. Если его позиция position считается с нуля, ниже находятся N - 1 - position продуктов. Номер продукта равен исходному индексу плюс один и не связан с его местом.
Просмотр второго срока уже размещённого продукта не меняет ни края, ни последний ответ. Время O(N log N), память O(N) на события и отметки.
Разбор на примере
Ввод
4 7 2 1 8 6 5 3 9
Вывод
3 1
| Срок | Продукт / сторона | Занятое место |
|---|---|---|
| 1 | 2, с начала | 1 |
| 2 | 1, с конца | 4 |
| 3 | 4, с начала | 2 |
| 5 | 3, с конца | 3; последнее размещение |
| 6, 7, 8, 9 | Повторные события | Пропускаем |
Срок 1 ставит продукт 2 в начало. Срок 2 ставит продукт 1 в конец. Срок 3 размещает продукт 4 на втором месте, срок 5 — продукт 3 на третьем. Остальные сроки относятся к уже размещённым продуктам. Итоговый рейтинг 2, 4, 3, 1: последним размещён продукт 3, ниже него один продукт.
Код на Python и C++
Различность всех сроков исключает неоднозначность одновременных событий. Нулевое число продуктов ниже последнего размещённого допустимо.
В C++ события — tuple<long long, int, int>, и sort сравнивает их так же, как кортежи в Python.
import sys
def solve(products):
n = len(products)
events = sorted((value, side, i)
for i, pair in enumerate(products)
for side, value in enumerate(pair))
used = [False] * n
left, right = 0, n - 1
last = position = 0
for value, side, i in events:
if used[i]:
continue
used[i] = True
last = i + 1
if side == 0:
position = left
left += 1
else:
position = right
right -= 1
return last, n - 1 - position
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
products = list(zip(data[1::2], data[2::2]))
print(*solve(products))
<algorithm>
<iostream>
<tuple>
<vector>
using namespace std;
int main() {
int n;
cin >> n;
// События (срок, сторона, индекс): сторона 0 — левый срок продукта, 1 — правый.
vector<tuple<long long, int, int>> events;
for (int i = 0; i < n; i++) {
long long first, second;
cin >> first >> second;
events.push_back({first, 0, i});
events.push_back({second, 1, i});
}
sort(events.begin(), events.end());
vector<bool> used(n, false);
int left = 0, right = n - 1;
int last = 0, position = 0;
for (auto [value, side, i] : events) {
if (used[i])
continue;
used[i] = true;
last = i + 1;
if (side == 0) {
position = left;
left += 1;
} else {
position = right;
right -= 1;
}
}
cout << last << ' ' << n - 1 - position << endl;
}
Типичные ошибки
- Разместить продукт дважды
После первого события used[i] становится True. Его второй срок уже ничего не делает.
- Вывести последнюю строку входа
Порядок размещения задаётся сроками, а идентификатор сохраняется из исходной нумерации.
- Вывести position как число стоящих ниже
Позиция отсчитывается от начала. Ниже находятся N - 1 - position, а не position продуктов.