ASTR2 - Editorial (2021 Headlines)

editorial
, ,
1

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;
}
``
1 Like