Что спрашивают
Каждая строка описывает одну единицу: артикул, цену и статус 0 — продана, 1 — осталась. Цена внутри артикула одинакова. Дорогим считается артикул с ценой строго выше среднего по всем единицам базы, включая непроданные.
Лидер дорогих выбирается по числу проданных, затем большей цене, затем меньшему остатку. Выведите выручку лидера и его остаток. N ≤ 10 000, цена ≤ 10 000, дорогие товары есть.
Приём решения
За один проход накопим сумму всех цен total и для каждого артикула сохраним цену, число проданных sold и оставшихся remaining. Среднее считается по N строкам, а не по числу различных артикулов.
Цена дорогая, если price * N > total. Умножение целых точно эквивалентно строгому сравнению со средним и не требует float. Далее среди дорогих сравним тройки (sold, price, -remaining) и выберем максимум.
Так сначала побеждает число продаж, потом цена и только затем меньший остаток. Нельзя сравнивать выручку раньше числа продаж: один дорогой проданный товар может дать больше денег, но всё равно проиграть по первому критерию.
После выбора вычислим sold * price и вернём remaining. Если несколько артикулов совпали по всем трём критериям, оба выходных числа у них одинаковы. Время O(N), память O(U), где U — число артикулов.
Разбор на примере
Ввод
11 2 40 1 1 10 0 3 40 0 2 40 0 4 100 0 1 10 0 2 40 1 3 40 0 1 10 0 2 40 0 1 10 0
Вывод
80 0
| Артикул | Продано / цена / осталось | Решение |
|---|---|---|
| 1 | 4 / 10 / 0 | 10 × 11 ≤ 380: не дорогой |
| 2 | 2 / 40 / 2 | Кандидат |
| 3 | 2 / 40 / 0 | Лучше по остатку |
| 4 | 1 / 100 / 0 | Меньше продаж |
Сумма цен 380, единиц 11, среднее примерно 34,55. Артикул 1 дешёвый и исключается. У артикулов 2 и 3 по две продажи и цена 40, но у 3 нет остатка, поэтому он побеждает. Артикул 4 дал выручку 100, однако продан только один раз. Ответ лидера: 2 × 40 = 80, остаток 0.
Код на Python и C++
По условию дорогие артикулы есть, даже если их продажи нулевые. Такие кандидаты участвуют в сравнении; выручка лидера тогда может быть нулём.
В C++ группы лежат в map<long long, array<long long, 3>>, а кандидаты сравниваются как tuple, в том же порядке, что кортежи в Python.
import sys
def solve(rows):
groups = {}
total = 0
for article, price, status in rows:
total += price
group = groups.setdefault(article, [price, 0, 0])
if status == 0:
group[1] += 1
else:
group[2] += 1
candidates = []
for price, sold, remaining in groups.values():
if price * len(rows) > total:
candidates.append((sold, price, -remaining))
sold, price, negative_remaining = max(candidates)
return sold * price, -negative_remaining
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
rows = list(zip(data[1::3], data[2::3], data[3::3]))
print(*solve(rows))
<algorithm>
<array>
<iostream>
<map>
<tuple>
using namespace std;
int main() {
int n;
cin >> n;
// groups[артикул] = {цена, продано, осталось}.
map<long long, array<long long, 3>> groups;
long long total = 0;
for (int i = 0; i < n; i++) {
long long article, price, status;
cin >> article >> price >> status;
total += price;
if (!groups.count(article))
groups[article] = {price, 0, 0};
if (status == 0)
groups[article][1] += 1;
else
groups[article][2] += 1;
}
tuple<long long, long long, long long> best = {-1, -1, 0};
for (auto& [article, group] : groups) {
auto [price, sold, remaining] = group;
if (price * n > total)
best = max(best, {sold, price, -remaining});
}
auto [sold, price, negative_remaining] = best;
cout << sold * price << ' ' << -negative_remaining << endl;
}
Типичные ошибки
- Перепутать значения статуса
Статус 0 обозначает проданный товар, 1 — оставшийся. Иначе одновременно изменятся продажи и остаток.
- Взять среднее по артикулам
Каждая единица имеет свой вес в среднем. Артикул из ста единиц учитывается сто раз.
- Выбрать максимальную выручку
Первый критерий — число проданных единиц. Выручка вычисляется только после выбора лидера.
- Включить цену на уровне среднего
Дорогая цена должна строго превышать среднее. Равенство price × N и total не подходит.