SOPC001 Editorial

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Math.

PROBLEM:

Given an array, find a set of students such that sum of all absolute values of differences against the maximum for each element is highest.

EXPLANATION:

The problem is straightforward: since differences are all positive, it is maximum when all the differences exist. Thus, one can take all the students with them.

However: difference is taken only against the maximum, thus if there are more than one person with the maximum value, none of them will get any books, so it is needed to leave all of them but one out, to take minimum number of people to the professor.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define max(a,b) ((a>b)?a:b)
using namespace std;
 
void solve()
{
    ll n,m;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    ll ans=0;
    for(ll i=0;i<n-1;i++)
        ans+=(a[n-1]-a[i]);
    ll cnt=0;
    for(ll i=0;i<n;i++)
    	if(a[i]==a[n-1])
    		cnt++;
    cout<<ans<<" "<<n-cnt+1<<endl;
}
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}