#include<bits/stdc++.h>
#define M 1000000007
#define ll long long int
#define ull long long int
#define pb push_back
using namespace std;
int main()
{
int t=1;
// cin>>t;
while(t--)
{
ull n,k;
cin>>n>>k;
ull a[n+1];for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n,greater<ull>());
ull ans=0,j=1;ull st=0;
ull z=n;
while(z>0)
{
// cout<<z<<" "<<st<<" "<<a[st]<<"\n";
for(ull i=st;i<min(st+k,n);i++)
{
ans+=a[i]*j;
}
st=min(st+k,n);
z=z-k;
j++;
}
cout<<ans<<"\n";
}
}
- Problem Description
You and K-1 friends want to buy N flowers. Each flower fi 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) * 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,…., cN-2, CN-1) for each flower fi.
Constraints
1 <= N, K <=100
1 <= ci <= 10^6
answer < 2^31
0 <= i <= N-1
Output Format
Print the minimum cost for buying N flowers.
- Test Case 1
Input (stdin)3 3
2 5 6
Expected Output13
- Test Case 2
Input (stdin)3 2
2 5 6
Expected Output15
Thanks for sharing. Great post very Informative, also checkout The Flower Shop
ReplyDelete