Что спрашивают
Раздел памяти вместимостью K в начале пуст. Если следующий запрос не помещается, сначала создаётся копия текущего содержимого и очищается раздел, затем записывается запрос. Время копии — время вызвавшего её запроса. При точном заполнении и в конце журнала копия не создаётся.
Найдите клиента с наибольшим объёмом за весь день и сумму двух наибольших копий не позднее 11:59:59. Ввод: N, K, затем время, клиент, объём. N ≤ 100 000, K < 10^6, каждый объём < K; времена в сутках различны. Лидер единственный, ранних копий хотя бы две.
Приём решения
Время ЧЧ:ММ:СС преобразуем в секунды: h * 3600 + m * 60 + s. Запросы сортируем по времени. Сумму каждого клиента считаем по всем строкам, включая вторую половину дня: этот ответ не ограничен утренней границей.
В проходе хранится used — занятый объём перед очередным запросом. Только при used + size > K создаётся копия объёма used; после этого used обнуляется и к нему прибавляется size текущего запроса. При равенстве копирования нет.
Если время копии не больше 43199 секунд, включим её в два наибольших объёма first и second. Новый объём не меньше first сдвигает прежний first во second. Иначе, если новый объём больше second, он заменяет second. Равные объёмы — разные копии, поэтому обе могут войти в сумму.
Порог относится к моменту копирования, а не к времени сохранённых в копии данных. Не добавляйте остаток раздела после последней строки. Время O(N log N), память O(N) на запросы и суммы клиентов; два максимума занимают O(1).
Разбор на примере
Ввод
8 10 12:00:00 7 2 02:00:00 8 4 20:00:00 7 9 05:00:00 7 2 01:00:00 7 6 11:59:59 9 9 03:00:00 7 3 04:00:00 8 6
Вывод
7 19
| Время запроса | Копия перед записью | Занято после записи |
|---|---|---|
| 01:00:00 | Нет | 6 |
| 02:00:00 | Нет: точное заполнение | 10 |
| 03:00:00 | 10, учитывается | 3 |
| 04:00:00 | Нет | 9 |
| 05:00:00 | 9, учитывается | 2 |
| 11:59:59 | 2, учитывается | 9 |
| 12:00:00 | 9, уже поздно | 2 |
| 20:00:00 | 2, уже поздно | 9; финальной копии нет |
В 02:00 раздел заполняется ровно до 10 без копирования. Утренние копии создаются в 03:00 объёмом 10, в 05:00 объёмом 9 и в 11:59:59 объёмом 2. Две наибольшие дают 19. Копия в 12:00 уже не учитывается. Клиент 7 передал за сутки 22, клиент 8 — 10, клиент 9 — 9; лидер 7.
Код на Python и C++
Клиентские суммы и объёмы копий относятся к разным группировкам данных. Их нужно считать независимо. Одинаковый размер двух копий не повод удалять повтор.
В C++ время hh:mm:ss разбирает sscanf(text.c_str(), "%d:%d:%d", &h, &m, &s), а суммы клиентов лежат в map. Лидер по условию единственный, поэтому порядок перебора клиентов не важен.
import sys
def solve(capacity, records):
totals = {}
for time, client, size in records:
totals[client] = totals.get(client, 0) + size
used = first = second = 0
for time, client, size in sorted(records):
if used + size > capacity:
if time <= 11 * 3600 + 59 * 60 + 59:
if used >= first:
first, second = used, first
elif used > second:
second = used
used = 0
used += size
return max(totals, key=totals.get), first + second
if __name__ == '__main__':
stream = sys.stdin
n, capacity = map(int, stream.readline().split())
records = []
for _ in range(n):
time, client, size = stream.readline().split()
h, m, s = map(int, time.split(':'))
records.append((h * 3600 + m * 60 + s, int(client), int(size)))
print(*solve(capacity, records))
<algorithm>
<cstdio>
<iostream>
<map>
<string>
<tuple>
<vector>
using namespace std;
int main() {
int n;
long long capacity;
cin >> n >> capacity;
vector<tuple<long long, long long, long long>> records(n);
map<long long, long long> totals;
for (auto& [time, client, size] : records) {
string text;
cin >> text >> client >> size;
int h, m, s;
sscanf(text.c_str(), "%d:%d:%d", &h, &m, &s);
time = h * 3600 + m * 60 + s;
totals[client] += size;
}
long long leader = 0, best = -1;
for (auto [client, total] : totals) {
if (total > best) {
best = total;
leader = client;
}
}
sort(records.begin(), records.end());
long long used = 0, first = 0, second = 0;
for (auto [time, client, size] : records) {
if (used + size > capacity) {
if (time <= 11 * 3600 + 59 * 60 + 59) {
if (used >= first) {
second = first;
first = used;
} else if (used > second) {
second = used;
}
}
used = 0;
}
used += size;
}
cout << leader << ' ' << first + second << endl;
}
Типичные ошибки
- Копировать при точном заполнении
Равенство used + size == K лишь заполняет раздел. Копирование произойдёт перед следующим не помещающимся запросом.
- Взять последние две ранние копии
Нужны две наибольшие по объёму, а не ближайшие к полудню. В примере последняя ранняя копия 2 не входит в ответ.
- Ограничить суммы клиентов утром
Наибольший переданный объём ищется за все сутки. Порог времени применяется только к копиям.
- Дописать копию в конце
После последней строки раздел не копируется автоматически. Такая копия не предусмотрена процедурой.