EJMAR21C-Editorial

PROBLEM LINK:

Practice
Author: Abhijeet Trigunait
Tester: Shekhar Srivastava

DIFFICULTY:

CAKEWALK.

PREREQUISITES:

Sorting.

PROBLEM:

Recently Chef decided to improve his shooting skills. So his coach offered him the following exercise. He placed N cans in a row on a table. Cans are numbered from left to right from 1 to N. Chef has to knock down each can exactly once to finish the exercise. He is allowed to choose the order in which he will knock the cans down.

Chef knows that the durability of the ith can is Ai. It means that if Chef has already knocked X cans down and is now about to start shooting the ith one, he will need (Ai*X+1) shots to knock it down. You can assume that if Chef starts shooting the ith can, he will be shooting it until he knocks it down.

Your task is to choose such an order of shooting so that the number of shots required to knock each of the N given cans down exactly once is minimum possible.

EXPLANATION:

We can see that because the multiplier X in the formula (Ai*X+1) is the position of the number and we want to minimize the sum of such formulas, the following greedy solution comes up to mind: because we want to count greater values as earlier as possible, let’s sort the array in decreasing order.

SOLUTIONS:

Setter's Solution
/* Author- Abhijeet Trigunait */



#include<bits/stdc++.h>

#define lld long long int

#define F first

#define S second

#define P pair<int,int>

#define pb push_back

#define mod 1e9+7

#define setbits(x) __builtin_popcountll(x)

#define zerobits(x) __builtin_ctzll(x)

#define gcd(x,y) __gcd(x,y)

#define endl '\n'



using namespace std;

int main(){

    int t;

    cin>>t;

    while(t--){

        lld n;

        cin>>n;

        lld arr[n];

        for(lld i=0;i<n;++i)cin>>arr[i];

        sort(arr, arr + n, greater<int>());

        lld cnt=0,ans=0;

        for(lld i=0;i<n;++i){

            ans+=cnt*arr[i]+1;

            ++cnt;

        }

        cout<<ans<<endl;



}

}

1 Like