Greedy Florist - Hacker Rank Solution

A group of friends want to buy a bouquet of flowers. The florist wants to maximize his number of new customers and the money he makes. To do this, he decides he'll multiply the price of each flower by the number of that customer's previously purchased flowers plus .

The first flower will be original price, , the next will be  and so on.

Given the size of the group of friends, the number of flowers they want to purchase and the original prices of the flowers, determine the minimum cost to purchase all of the flowers.

For example, if there are  friends that want to buy  flowers that cost  each will buy one of the flowers priced  at the original price. Having each purchased  flower, the first flower in the list, , will now cost . The total cost will be .

Function Description

Complete the getMinimumCost function in the editor below. It should return the minimum cost to purchase all of the flowers.

getMinimumCost has the following parameter(s):

• c: an array of integers representing the original price of each flower
• k: an integer, the number of friends

Input Format

The first line contains two space-separated integers  and , the number of flowers and the number of friends.
The second line contains  space-separated positive integers , the original price of each flower.

Constraints

Output Format

Print the minimum cost to buy all  flowers.

Sample Input 0

3 3
2 5 6

Sample Output 0

13

Explanation 0

There are  flowers with costs  and  people in the group. If each person buys one flower, the total cost of prices paid is  dollars. Thus, we print  as our answer.

Sample Input 1

3 2
2 5 6

Sample Output 1

15

Explanation 1

There are  flowers with costs  and  people in the group. We can minimize the total purchase cost like so:

1. The first person purchases  flowers in order of decreasing price; this means they buy the more expensive flower () first at price  dollars and the less expensive flower () second at price dollars.
2. The second person buys the most expensive flower at price  dollars.

We then print the sum of these purchases, which is , as our answer.

Sample Input 2

5 3
1 3 5 7 9

Sample Output 2

29

Explanation 2

The friends buy flowers for ,  and ,  and  for a cost of .

Greedy Florist - Hacker Rank Solution

From the problem statement, we make two observations:

1. The more flowers a customer has already bought, the more dollars one needs to pay. We want to minimize the maximum number of flowers any friend buys, so the purchases will be as evenly distributed as possible.

2. We also need to optimize the order in which we purchase these flowers. The amount of additional money we need to pay later is linear in . We want to buy the most expensive flowers first, at the lower multiple.

Based on these observations, we know that we first need to sort the price of flowers in decreasing order, and then distribute these flowers evenly amongst our friends buying the most expensive first.

//flowers.cpp
//Flowers
//Algorithms - Search
//Author: derekhh

#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;

int c[100];

int main()
{
    int n, k;
    long long ans = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    sort(c, c + n, greater<int>());
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        ans += c[i] * (cnt / k + 1);
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

---

#include<iostream>
#include<queue>
using namespace std;

int main(void){
    int N, K, price;
    long long int totalAmount = 0;
    priority_queue<int> prices;
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> price;
        prices.push(price);
    }

    int x;
    for (x = 0; x < N; ++x) {
            totalAmount += (x / K + 1) * prices.top();
            prices.pop();

    }

    cout << totalAmount << "\n";
    return 0;
}