Что спрашивают
Корабль вмещает груз массой не больше S. Из N контейнеров нужно перевезти как можно больше, а среди таких способов оставить на космодроме наибольшую суммарную массу.
Выведите количество и массу оставшихся контейнеров. S ≤ 100 000, N ≤ 10 000, масса каждого от 1 до 100; сумма всех масс больше S. Мест достаточно, ограничивает только масса.
Приём решения
Сначала отделим два критерия. Максимальная масса оставшегося груза равна общей массе минус минимальная масса перевезённого груза. Поэтому после максимизации количества выгодно брать именно самые лёгкие контейнеры.
Отсортируйте массы по возрастанию. Набирайте контейнеры, пока очередной помещается: used + weight <= S. Если очередной не поместился, последующие ещё тяжелее, и набор можно закончить.
Почему это даёт максимум количества? Сумма первых k масс не больше суммы любых других k. Если даже k самых лёгких не помещаются, никакие k контейнеров перевезти нельзя. Тот же префикс одновременно минимизирует перевезённую массу при найденном количестве.
Пусть взято k контейнеров массой used. Ответ: N - k и sum(weights) - used. Сортировка занимает O(N log N) времени и O(N) памяти. При небольших массах возможен также подсчёт количества контейнеров каждого веса.
Разбор на примере
Ввод
19 5 9 4 7 3 11
Вывод
2 20
| Контейнер | Масса на корабле | Решение |
|---|---|---|
| 3 | 3 | Берём |
| 4 | 7 | Берём |
| 7 | 14 | Берём |
| 9 | 23 > 19 | Останавливаемся |
После сортировки получаем 3, 4, 7, 9, 11. Первые три весят 14, а первые четыре — 23, что больше 19. Перевезём три контейнера; останутся два контейнера массами 9 и 11, всего 20. Если заменить 7 на 11, перевезённых тоже будет три, но оставшаяся масса уменьшится до 16.
Код на Python и C++
Если ни один контейнер не помещается, count и used остаются нулевыми. Этот случай разрешён: на космодроме остаётся весь груз.
В C++ общая масса считается при чтении, вместо sum(weights).
import sys
def solve(capacity, weights):
used = count = 0
for weight in sorted(weights):
if used + weight > capacity:
break
used += weight
count += 1
return len(weights) - count, sum(weights) - used
if __name__ == '__main__':
capacity, n, *weights = map(int, sys.stdin.buffer.read().split())
print(*solve(capacity, weights))
<algorithm>
<iostream>
<vector>
using namespace std;
int main() {
long long capacity;
int n;
cin >> capacity >> n;
vector<long long> weights(n);
long long total = 0;
for (long long& weight : weights) {
cin >> weight;
total += weight;
}
sort(weights.begin(), weights.end());
long long used = 0;
int count = 0;
for (long long weight : weights) {
if (used + weight > capacity)
break;
used += weight;
count += 1;
}
cout << n - count << ' ' << total - used << endl;
}
Типичные ошибки
- Увеличивать массу перевезённых
Здесь максимизируется масса оставшихся. Замена последнего лёгкого контейнера на более тяжёлый ухудшает второй ответ.
- Вывести количество на корабле
Спрашивают про оставшиеся контейнеры. Из общего количества нужно вычесть count.
- Запретить точное заполнение
Общая масса может быть ровно S. Условие остановки — строгое превышение вместимости.