CMED203 - Editorial

PROBLEM LINK:

Practice

DIFFICULTY:

CakeWalk-Easy

PREREQUISITES:

None at all image

PROBLEM:

A bag contains K number of balls and each ball having a different integer written on it. Man chooses pair of balls having adjacent integers written on them from the bag and removes the ball having a bigger number written from one of these two and this lessens the number of balls in the bag by one.
The cost of his action will be equal to the ball having a smaller integer written on it from two of them.

Find the minimum sum of costs of actions needed to change the number of balls in the bag to one.

EXPLANATION:

In order to minimize the total cost, He should surely choose the pair of balls having consecutive integers written on them consisting of the smallest integer from the bag.

The ball on which the minimum number is written will anyway be the last remaining ball after all operations have been applied. So, why not choose a pair of consecutive integer balls involving this minimum integer ball till the number of balls in a bag reduces to one and that last one ball will be the ball having minimum integer written on it.

Since we need to perform this operation K −1 times, the total cost incurred will hence be equal to (K - 1)*(MINVAL). As the answer can be a little large, use a data type that can handle larger numbers.

SOLUTIONS:

Solution
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
int main()
{
ll int t;
scanf("%lld",&t);
while(t--)
{
    ll int n;
    scanf("%lld",&n);
    vector<ll int> v(n);
    
    for(ll int i=0;i<n;i++)
    {
        scanf("%lld",&v[i]);
    }
    sort(v.begin(),v.end());
   
    
    cout<<(n-1)*v[0]<<endl;
  
   
}    
return 0;
}