Problem Statement
You and your K-1 friends want to buy N flowers. Flower number i has cost ci.
Unfortunately the seller does not want just one customer to buy a lot
of flowers, so he tries to change the price of flowers for customers who
have already bought some flowers. More precisely, if a customer has
already bought x flowers, he should pay (x+1)*ci dollars to buy flower number i.
You and your K-1 friends want to buy all N flowers in such a way that you spend the least amount of money. You can buy the flowers in any order.
Input:
The first line of input contains two integers N and K (K <= N). The next line contains N space separated positive integers c1,c2,...,cN.
Output:
Print the minimum amount of money you (and your friends) have to pay in order to buy all N flowers.
Constraints
1≤N,K≤100
Anyci is not more than 106
Result is guaranteed to be less than231
Sample input #00
Sample Case #00: In this example, all of you should buy one flower each. Hence, you'll have to pay 13 dollars.
Sample Case #01: Here one of the friend buys first two flowers in decreasing order of their price. So he will pay
You and your K-1 friends want to buy all N flowers in such a way that you spend the least amount of money. You can buy the flowers in any order.
Input:
The first line of input contains two integers N and K (K <= N). The next line contains N space separated positive integers c1,c2,...,cN.
Output:
Print the minimum amount of money you (and your friends) have to pay in order to buy all N flowers.
Constraints
Any
Result is guaranteed to be less than
Sample input #00
3 3
2 5 6
Sample output #0013
Sample input #01 3 2
2 5 6
Sample output #0115
Explanation : Sample Case #00: In this example, all of you should buy one flower each. Hence, you'll have to pay 13 dollars.
Sample Case #01: Here one of the friend buys first two flowers in decreasing order of their price. So he will pay
(0+1)*5 + (1+1)*2 = 9
. And other friend will buy the costliest flower of cost 6
. So total money need is 9+6=15
.MY SOLUTION:
#include<stdio.h>
int sort(const void *a,const void *b)
{
return(*(int *)a-*(int *)b);
}
int main(){
int n,k,i;
scanf("%d %d",&n,&k);
int a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(a,n,sizeof(int),sort);
int result=0,flower=0;
for(i=0;i<n;i++)
{
flower=i/k;
result+=(flower+1)*a[(n-1)-i];
}
printf("%d",result);
return 0;
}