Problem: Greedy Florist

*Difficulty: Easy

Problem:

You and K – 1 friends want to buy N flowers. Each fi flower has some cost ci . 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 fi  is  Pfi  = (x+1) x ci .

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^6
answer < 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:
Screen Shot 2016-07-16 at 12.02.24 PM
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:
Screen Shot 2016-07-16 at 12.07.23 PM
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
Advertisements