## PROBLEM LINK

Practice

Contest

Setter: Aishwarya Babu

Editorialist: Aishwarya Babu

## DIFFICULTY

Simple

## PREREQUISITES

Greedy

## PROBLEM

N asteroids are approaching Earth. You have K plasma blasters that can destroy 1 asteroid with each shot. The cost of each shot is defined as (x+1)*S where

x - number of blasts already fired

S - size of asteroid

Find the minimum cost with which we can save the planet.

## EXPLANATION

From the problem, we can observe that with each shot, the cost increases. So we need to evenly distribute the asteroids to each plasma blaster. We also need to optimize the order in which we destroy the asteroids, that is, we want to destroy the bigger asteroids first then proceed with the smaller one.

Based on these observations, we use a greedy approach to distribute the asteroids evenly based on the descending order of sizes.

## Setter’s solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
int c[100];
while(t--) {
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;
}
``
```