Что спрашивают

Посылки грузят в заданном порядке выбора: самую тяжёлую из помещающихся, затем самую лёгкую из оставшихся, и снова чередуют эти действия. Погрузка заканчивается, когда ничего больше не помещается.

Нужно вывести число погружённых посылок и массу последней. На входе 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
Лёгкая47
Тяжёлая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))
#include <algorithm>
#include <iostream>
#include <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;
}

Типичные ошибки

  • Остановиться на слишком тяжёлой

    На тяжёлом ходе нужно поискать меньшую посылку. Неподходящая максимальная масса ещё не означает конец погрузки.

  • Всё время брать лёгкие

    Это увеличивает количество, но нарушает заданное чередование. В этой задаче моделируют процедуру.

  • Переключить ход после пропуска

    Ход меняется только после погрузки. Пропуск неподходящей массы не расходует ход.