Что спрашивают
Посылки грузят в заданном порядке выбора: самую тяжёлую из помещающихся, затем самую лёгкую из оставшихся, и снова чередуют эти действия. Погрузка заканчивается, когда ничего больше не помещается.
Нужно вывести число погружённых посылок и массу последней. На входе N, S, затем N масс. N ≤ 100 000, S ≤ 10^9, массы ≤ 10 000. Хотя бы одна посылка помещается.
Приём решения
Здесь правило уже задано, поэтому искать набор с максимальным количеством не нужно. Отсортируем массы и будем хранить левую и правую границы ещё не рассмотренной части массива.
На тяжёлом ходе двигаем правую границу влево, пока масса больше остатка грузоподъёмности. Эти посылки можно отбросить навсегда: свободная вместимость дальше только уменьшается. Берём первую помещающуюся справа.
На лёгком ходе проверяем левую массу. Если даже она не помещается, закончить можно сразу. После каждой погрузки вычитаем массу, запоминаем её и переключаем ход. Пропуск слишком тяжёлой посылки ходом не считается.
Каждый указатель проходит массив не больше одного раза. После сортировки моделирование занимает O(N), всё решение — O(N log N) времени и O(N) памяти. Равные массы остаются отдельными элементами.
Разбор на примере
Ввод
6 23 9 4 12 6 30 5
Вывод
3 6
| Ход | Выбранная масса | Свободно после погрузки |
|---|---|---|
| Тяжёлая | 12; 30 пропущена | 11 |
| Лёгкая | 4 | 7 |
| Тяжёлая | 6; 9 пропущена | 1 |
| Лёгкая | 5 не помещается | Конец |
Масса 30 не помещается с самого начала. Первой погрузим 12, затем самую лёгкую посылку 4. Осталось 7: посылка 9 не подходит, но 6 подходит. После неё остаётся 1, меньше любой оставшейся массы. Получились три посылки, последняя весит 6.
Код на Python и C++
Две границы относятся к отсортированному массиву. Удалять элементы из начала списка не требуется: достаточно увеличивать left.
import sys
def solve(capacity, weights):
weights = sorted(weights)
left, right = 0, len(weights) - 1
heavy = True
count = last = 0
while left <= right:
if heavy:
while left <= right and weights[right] > capacity:
right -= 1
if left > right:
break
last = weights[right]
right -= 1
else:
if weights[left] > capacity:
break
last = weights[left]
left += 1
capacity -= last
count += 1
heavy = not heavy
return count, last
if __name__ == '__main__':
n, capacity, *weights = map(int, sys.stdin.buffer.read().split())
print(*solve(capacity, weights))
<algorithm>
<iostream>
<vector>
using namespace std;
int main() {
int n;
long long capacity;
cin >> n >> capacity;
vector<long long> weights(n);
for (long long& weight : weights)
cin >> weight;
sort(weights.begin(), weights.end());
int left = 0, right = n - 1;
bool heavy = true;
int count = 0;
long long last = 0;
while (left <= right) {
if (heavy) {
while (left <= right && weights[right] > capacity)
right -= 1;
if (left > right)
break;
last = weights[right];
right -= 1;
} else {
if (weights[left] > capacity)
break;
last = weights[left];
left += 1;
}
capacity -= last;
count += 1;
heavy = !heavy;
}
cout << count << ' ' << last << endl;
}
Типичные ошибки
- Остановиться на слишком тяжёлой
На тяжёлом ходе нужно поискать меньшую посылку. Неподходящая максимальная масса ещё не означает конец погрузки.
- Всё время брать лёгкие
Это увеличивает количество, но нарушает заданное чередование. В этой задаче моделируют процедуру.
- Переключить ход после пропуска
Ход меняется только после погрузки. Пропуск неподходящей массы не расходует ход.