C++. Коллекционирование этикеток

Question

Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K1, K2, ..., KN этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?

Формат ввода

В первой строке содержится число N – количество альбомов. Во второй строке идет N чисел K1, K2, ..., KN, задающих вместимости альбомов. N – натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.

Формат вывода

Выведите сначала число E – максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел – каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.

Входные данные

4    
1 2 1 1

Выходные данные

2
1 2
2 3

Я пытался сделать вот так:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n, max_ = -1, s = 0;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        max_ = max(a[i], max_);
        s += a[i];
    }
    ll e = min(s / 2, s - max_);
    cout << e << "\n";

    for (ll i = 0; i < n - 1; i++) {
        for (ll j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                ll k = a[j];
                a[j] = a[j + 1];
                a[j + 1] = k;
                cout << j << " " << j + 1 << "\n";
            }
        }
    }

    return 0;
}

Как я понял эта задача решается с помощью инверсий. Нужно вывести индексы "инверсированных" элементов в массиве вместительностей альбомов. А что делать если массив вместительностей альбомов уже отсортирован? Большое спасибо!

P.S. Возможно решение будет лучше, если использовать сортировку слиянием, но как поменять ее для текущей задачи - я не понял.

Answer 1

В комментарий все не поместится, поэтому как ответ выложу идею.

Попробуйте сделать самое простое, что приходит в голову это сделать вектор пар, где первое число будет размер альбома, а второе число это номер альбома.

Например:

//Вектор<пара<вместимость альбома, его номер>>
vector<pair<ll, ll>> a(n);

Тогда главный цикл будет выглядеть примерно вот так:

vector<pair<ll, ll>> a(n);
ll a_;
for (ll i = 0; i < n; i++) {
    cin >> a_;
    max_ = max(a_, max_);
    s += a_;
    a[i] = make_pair(a_, i + 1);
}
ll e = min(s / 2, s - max_);

И тогда самым лучшим решением будет использовать функцию sort

sort(a.begin(), a.end());

После этой функции вектор a будет отсортирован по вместимости альбома, а если вместимость одинакова, то по его номеру.

И самое простое и банальное решение, которое я хотел бы, чтобы вы проверили пройдет ли она тесты:

for (int i = 0; i < e; ++i) {
    cout << (a[n - 1].second + 1) << " " << (a[n - 2].second + 1) << "\n";
    --a[n - 1].first;
    --a[n - 2].first;
    sort(a.begin(), a.end());
}

Идея думаю понятна. Берем 2 максимальных по вместимости альбома и заносим в неё этикетку, далее сортируем.

Answer 2

Инверсии во входном списке размеров не могут влиять на размер ответа: количество наклеек в коллекции не зависит от расстановки альбомов на полке.

Я заимствовал идею из ответа (Павел Ериков): берем два самых больших альбома, помещаем в них пару наклеек, уменьшаем объёмы этих альбомов. Повторять, пока у нас осталось хотя бы два непустых альбома.

Для выборки максимума подходит очередь с приоритетами. В С++ priority_queue выдаёт максимальный элемент.

Общая сложность решения NlogM (N - вместимость альбомов, M - число альбомов), так как операции с очередью приоритетов логарифмические. Я думаю что от логарифма можно избавится - очередь с приоритетатми тут в качестве пушки при воробьях.

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

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

// g++ -std=c++11 -pedantic -Wall -Wextra label_collectioning.cpp

#include <iostream>
#include <queue>


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;

    std::priority_queue<std::pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        int k;
        std::cin >> k;
        q.emplace(k, i + 1);
    }

    std::vector<std::pair<int, int>> output;

    while (q.size() > 1) {
        auto a1 = q.top();
        q.pop();
        auto a2 = q.top();
        q.pop();
        output.emplace_back(a1.second, a2.second);
        if (a1.first > 1) {
            q.emplace(a1.first - 1, a1.second);
        }
        if (a2.first > 1) {
            q.emplace(a2.first - 1, a2.second);
        }
    }

    std::cout << output.size() << '\n';
    for (auto p : output) { 
        std::cout << p.first << ' ' << p.second << '\n';
    }
    return 0;
}

БЛОГ НА HUSL

C++. Коллекционирование этикеток

Ответы (2 шт):