HackerRank: Flowers
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.
1. The additional flowers a customer has already bought, the additional dollars one needs to pay. Therefore, we need to try our best to "evenly distribute" the flowers between these K people.
2. We also need to optimize the order in which we purchase these flowers. The amount of additional money we need to pay later is linear in ci. So if we have already bought x flowers, the natural expectation is that the next flower we buy is as cheap as possible.
Based on these observations, we know that we first need to sort the price of flowers in decreasing order, and then distribute these flowers evenly amongst our friends.
Scanner in = new Scanner(System.in);
int n, k;
n = in.nextInt();
k = in.nextInt();
https://codepair.hackerrank.com/paper/RaskgDrw?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
StringTokenizer s1=new StringTokenizer(a);
int n=Integer.parseInt(s1.nextToken());
int m=Integer.parseInt(s1.nextToken());
int a1[]=new int[n];
String x=br.readLine();
StringTokenizer x1=new StringTokenizer(x);
for(int i=0;i<n;i++)
{
a1[i]=Integer.parseInt(x1.nextToken());
}
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.
1. The additional flowers a customer has already bought, the additional dollars one needs to pay. Therefore, we need to try our best to "evenly distribute" the flowers between these K people.
2. We also need to optimize the order in which we purchase these flowers. The amount of additional money we need to pay later is linear in ci. So if we have already bought x flowers, the natural expectation is that the next flower we buy is as cheap as possible.
Based on these observations, we know that we first need to sort the price of flowers in decreasing order, and then distribute these flowers evenly amongst our friends.
int main()
{
int n, k;
long long ans = 0;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> c[i];
sort(c, c + n, greater<int>());
int cnt = 0;
for (int i = 0; i < n; i++)
{
ans += c[i] * (cnt / k + 1);
cnt++;
}
cout << ans << endl;
return 0;
}
https://codepair.hackerrank.com/paper/6JGHORGV?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9Scanner in = new Scanner(System.in);
int n, k;
n = in.nextInt();
k = in.nextInt();
https://codepair.hackerrank.com/paper/RaskgDrw?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
StringTokenizer s1=new StringTokenizer(a);
int n=Integer.parseInt(s1.nextToken());
int m=Integer.parseInt(s1.nextToken());
int a1[]=new int[n];
String x=br.readLine();
StringTokenizer x1=new StringTokenizer(x);
for(int i=0;i<n;i++)
{
a1[i]=Integer.parseInt(x1.nextToken());
}