## Problem: Greedy Florist

*Difficulty: Easy

Problem:

You and K – 1 friends want to buy N flowers. Each **f***i* flower has some cost **c***i* . The florist is greedy and wants to maximize his number of new customers, so he increases the sale price of flowers for repeat customers; more precisely, if a customer has already purchased x flowers, price P for **f***i* is Pfi = (x+1) x **c***i* .

Find and print the minimum cost for your group to purchase N flowers.

**Note:** You can purchase the flowers in any order.

**Input Format**

The first line contains two integers, N (number of flowers to purchase) and K (the size of your group of friends, including you).

The second line contains N space-separated positive integers describing the cost (c0,c1,..c(N-1)) for each flower .

**Constraints**

1 <= N,K <= 100

1 <=ci <= 10^6answer < 2^31

0 <= i <= N-1

**Output Format**

Print the minimum cost for buying flowers.

**Sample Input 0**

`3 3 2 5 6`

**Sample Output 0**

`13`

**Sample Input 1**

`3 2 2 5 6`

**Sample Output 1**

`15`

**Explanation**

*Sample Case 0:*

There are flowers and people in your group. Each person buys one flower and the sum of prices paid is dollars, so we print .

*Sample Case 1:*

There are flowers and people in your group. The first person purchases flowers, and , in order of decreasing price; this means they buy the more expensive flower first at price Pf1 = (0+1) x 5 = 5 dollars and the less expensive flower second at price Pf0 = (1+1) x 2 = 4 dollars. The second person buys the most expensive flower at price Pf2 = (0+1)x6 dollars . We print the sum of these purchases (5+4+6), which is 15.

How to solve:

This problem can be solved by using ordinal principle in heuristic.

Given a set of input and k groups, your task is finding a proper order of the input such that after distributing all elements in the input set into k groups, you achieve something as smallest or least as possible.

For example you’re given a set of n works, each work can be done in wi hours, and k machines. Your work is assign works to machines so that the time to complete those works is smallest ( or shortest).

The order could be ascending or descending, depend on the problem.

Let say k flowers is in the list **flowers**, and you and k-1 friends is in the list **group – each intialized with zero .**

Here to solve this problem, you sort the** flowers** list in descending order base on their cost in dollar. Go through **flowers** list, assign each value to an element in group list, and the element in the group list must have the lowest value at that moment.

Here’s an example:

5 2

1 2 7 9 100

We got 2 flowers and 2 people.

First we sort it in descending order :

100 9 7 2 1

p1 : paid = 0, purchased = 0

p2 : paid = 0, purchased = 0

For 100 we can assign it to any person

p1 : paid = 100, purchased = 1

p2 : paid = 0, purchased = 0

For 9, at the moment, p1 has the lowest paid value, so we assign 9 to p1

p1 : paid = 100, purchased = 1

p2 : paid = 9, purchased = 1

For 7, p1 still has the lowest paid value, so we assign (1+1)*7 to p1

p1 : paid = 100, purchased = 1

p2 : paid = 9 + (1+1)*7 = 23, purchased = 2

For 2, p1 still has the lowest paid value, so we assign (2+1)*2 to p1

p1 : paid = 100, purchased = 1

p2 : paid = 23 + (2+1)*2 = 29 , purchased = 3

For 1, likewise, we assign (3+1)*1 to p1

p1 : paid = 100, purchased = 1

p2 : paid = 29 + (3+1)*1 = 33, purchased = 4

The total money that you and your friends have to pay to buy those 5 flowers is 100 + 33 = 133. Easy, isn’t it? But here is the problem, the answer for this example is 130. Here is what we need to change : Checking for the smallest paid is not enough, you have to check if that person buys that flower, then how many money cost in total, if that money is the smallest ?

So here is the implementation in Python2:

**l** is the list of people, each people is a dict {‘purchased’:0, ‘paid’:0}, **cost** is the money cost for the current flower, **total** is the current cost of all flowers that’ve been purchased.

**min_value** here is the min of money cost in total after someone purchase new flower with the cost in the arguments.

Go through each person :

—-check if that person buy that flower will end up with the smallest total money cost:

——–then mark it as the smallest total money cost

——–and mark which person

then return the person ( the person that buy that flower lead to the smallest money cost in total)

Here’s the main method:

If the number of flowers smaller or equal with the number of people, then we just return the sum of all those flowers.

Bonus: Big test case

Input

60 18 120854 100862 523789 849072 23733 355147 660925 59103 801528 607947 51312 754005 823629 876280 23088 668838 214629 641310 66064 541147 97284 579336 319949 193067 35064 227785 376976 146458 258150 551784 961936 189099 552128 318057 39381 41667 316754 680180 681303 7132 472252 791845 540485 464674 336442 572655 724577 627822 553055 986861 944776 588636 966817 892103 737744 478475 668429 809085 362250 597680

Output:

46361218

## Reply