Codeforces 2161C — Loyalty (1200)

Сложность: 1200 | Теги: greedy, math, simulation

Условие

Вы — покупатель в магазине, который хочет купить n предметов. Цена каждого предмета i равна a[i], причем 1 ≤ a[i] ≤ X, где X — это фактор лояльности.

Если после покупки предмета с ценой p ваш уровень лояльности увеличивается, вы получаете p бонусных очков.

Ваша задача — найти максимальное количество бонусных очков, которое можно получить, выбрав оптимальный порядок покупки предметов.

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

Первая строка содержит количество тестов t. Каждый тест состоит из двух строк:

• n и X (количество предметов и фактор лояльности)
• Массив a — цены предметов

Пример

Input:
1
10 2
1 2 1 2 1 2 1 2 1 2

Output:
12
1 2 2 2 2 2 1 1 1 1

Идея решения

Чтобы максимизировать бонусные очки, нужно использовать жадный алгоритм. Уровень лояльности увеличивается, когда сумма S пересекает границу, кратную X.

Стратегия:

• Если добавление самого дорогого предмета повысит уровень лояльности — берём его (получим максимум очков).
• Если это не повышает уровень лояльности — берём самый дешёвый предмет, чтобы быстрее набрать сумму до следующего порога X.

Для эффективного поиска минимума и максимума используем std::multiset.

Код на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long X;
        cin >> n >> X;
        
        multiset<int> a;
        for (int i = 0; i < n; ++i) {
            int val;
            cin >> val;
            a.insert(val);
        }
        
        long long nowSum = 0, ans = 0;
        vector<int> ans_posl;
        ans_posl.reserve(n);
        
        for (int i = 0; i < n; ++i) {
            auto itMax = a.end(); --itMax;
            auto itMin = a.begin();
            
            // Проверяем, повысит ли самый дорогой товар уровень лояльности
            if (nowSum / X < (nowSum + *itMax) / X) {
                nowSum += *itMax;
                ans += *itMax;
                ans_posl.push_back(*itMax);
                a.erase(itMax);
            } else {
                // Иначе берем самый дешевый, чтобы быстрее дойти до следующего порога
                nowSum += *itMin;
                ans_posl.push_back(*itMin);
                a.erase(itMin);
            }
        }
        
        cout << ans << '\n';
        for (int x : ans_posl) cout << x << ' ';
        cout << '\n';
    }
}<

Сложность

• Время: O(n log n) — вставка в multiset и удаление элементов занимают логарифмическое время
• Память: O(n) — хранение элементов в наборе и ответе

Это решение проходит в заданных ограничениях (2 секунды на 2 * 10^4 тестов).