Это одна из задач средней сложности в разделе Жадные алгоритмы набора задач Hackerrank для подготовки к собеседованию. Ссылка здесь.

Задача состоит в том, что k друзей хотят купить все цветы, имеющиеся в магазине. Однако флорист отслеживает покупки каждого человека, чтобы скорректировать цену на следующий цветок, который они покупают. Цена цветка указана
P(flower_price, prev_purch) = flower_price*(1+prev_purch) . Друзья хотят купить все цветы вместе и минимизировать затраты.

Решение

Чтобы решить эту проблему, нам нужно отсортировать базовые цены на цветы в порядке возрастания или убывания. Какой вам больше нравится. Мне нравится перебирать массивы снизу вверх, поэтому я выбрал убывающую цену. Теперь нам нужен массив для отслеживания покупок друзей, инициализированных нулями. Мы можем получить минимальную стоимость, выбрав (i%k)th человека, который купит ith самый дорогой цветок, и добавим скорректированную цену в наше решение. После этого мы добавляем единицу к покупкам (i%k)th человека, чтобы в следующий раз, когда он будет покупать цветок, флорист взимал скорректированную цену.

Код

Ссылка на решение на github

static bool sortFn (int i, int j) { return (i>j); }
static int purchases[100];
int getMinimumCost(int k, vector<int> c) {
    
    int cost = 0;
    int n = c.size();
    sort(c.begin(), c.end(), sortFn);
    
    for(int i = 0; i < n; i++){     
        cost+=c[i]*(purchases[i%k]+1);
        purchases[i%k]++;
    }
    
    return cost;
}