Это одна из задач средней сложности в разделе Жадные алгоритмы набора задач Hackerrank для подготовки к собеседованию. Ссылка здесь.
Задача состоит в том, что k друзей хотят купить все цветы, имеющиеся в магазине. Однако флорист отслеживает покупки каждого человека, чтобы скорректировать цену на следующий цветок, который они покупают. Цена цветка указана P(flower_price, prev_purch) = flower_price*(1+prev_purch)
. Друзья хотят купить все цветы вместе и минимизировать затраты.
Решение
Чтобы решить эту проблему, нам нужно отсортировать базовые цены на цветы в порядке возрастания или убывания. Какой вам больше нравится. Мне нравится перебирать массивы снизу вверх, поэтому я выбрал убывающую цену. Теперь нам нужен массив для отслеживания покупок друзей, инициализированных нулями. Мы можем получить минимальную стоимость, выбрав (i%k)th
человека, который купит ith
самый дорогой цветок, и добавим скорректированную цену в наше решение. После этого мы добавляем единицу к покупкам (i%k)th
человека, чтобы в следующий раз, когда он будет покупать цветок, флорист взимал скорректированную цену.
Код
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; }