Problem Links:
Link;Problem:
You and your K-1 friends want to buy N flowers. Flower number i has host ci. Unfortunately the seller does not like a customer to buy a lot of flowers, so he tries to change the price of flowers for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*cidollars to buy flower number i.
You and your K-1 firends want to buy all N flowers in such a way that you spend the as few money as possible.
Input:
You and your K-1 firends want to buy all N flowers in such a way that you spend the as few money as possible.
Input:
The first line of input contains two integers N and K.
next line contains N positive integers c1,c2,...,cN respectively.
Output:
next line contains N positive integers c1,c2,...,cN respectively.
Output:
Print the minimum amount of money you (and your friends) have to pay in order to buy all n flowers.
Sample onput :
3 3
2 5 6
2 5 6
Sample output :
13
Explanation :
In the example each of you and your friends should buy one flower. in this case you have to pay 13 dollars.
In the example each of you and your friends should buy one flower. in this case you have to pay 13 dollars.
Constraint :
1 <= N, K <= 100
Each ci is not more than 1000,000
Each ci is not more than 1000,000
Solution:
Here, 1st, sort the array, then use greedy to collect flowers from the largest cost, since the later you collect the high price flower, that will cost you more.
Source Code:
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; /** * */ /** * @author antonio081014 * @time Oct 6, 2012, 11:57:39 PM */ public class Solution { public static void main(String[] args) throws Exception { Solution main = new Solution(); main.run(); System.exit(0); } public void run() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split("\\s"); int N = Integer.parseInt(str[0]); int K = Integer.parseInt(str[1]); str = br.readLine().split("\\s"); int[] cost = new int[N]; for (int i = 0; i < N; i++) { cost[i] = Integer.parseInt(str[i]); } Arrays.sort(cost); int total = 0; int _K, i; for (i = N - 1, _K = K; i >= 0 && _K > 0; i--, _K--) { total += cost[i]; } int index = 0; int round = 1; for (; i >= 0; i--) { total += cost[i] * (round + 1); index++; if (index >= K) { round++; index = 0; } } System.out.println(total); } }