Решение задачи "Экономия" с Acmp

Без пояснения   Просмотров: 15


Представь, что ты - капитан команды, которая только что выиграла мировой финал ACM ICPC, и теперь тебе предстоит отпраздновать свою победу со своими друзьями, которых у тебя ровно K-1. Для этого необходимо закупить N бутылок любимого напитка (остается только догадываться какого) в ближайшем магазине. Стоимость i-й бутылки составляет Ci рублей. К сожалению, продавец не любит, когда его клиенты покупают слишком много бутылок, поэтому он продаёт только по одной бутылке за раз, а также изменяет цену бутылки для клиента, который ранее у него уже делал покупки. Точнее, если клиент уже купил X бутылок, то он должен заплатить (X+1)*Ci рублей, чтобы купить бутылку номер i.

Необходимо определить минимально возможную стоимость приобретения N бутылок с учетом того, что в процессе покупки могут участвовать не более K человек (только ты и твои друзья).

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long n,k, s = 0;
    cin >> n >> k;
    vector<long long> a(n);
    vector<long long> res(k);
    for(auto &i : a){
        cin >> i;
    }
    sort(a.begin(), a.end());
    for(int i = 0; i < res.size(); ++i){
        for(int j = a.size() - 1 - i; j >= 0; j -= k){
            s += (res[i] + 1) * a[j];
            ++res[i];
        }
    }
    cout << s;
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться