InterviewStreet: Flowers

Problem Links:

Link;

Problem:

You and your K-1 friends want to buy N flowers. Flower number i has host c_i. 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)*c_idollars 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:

The first line of input contains two integers N and K.
next line contains N positive integers c₁,c₂,...,c_N 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

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.

Constraint :

1 <= N, K  <= 100
Each c_i 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);
 }
}