SAVECTK - Editorial

editorial
,
1

PROBLEM LINK:

Practice

EXPLANATION:

We can see that order of elements in the array A doesn’t affect the number of operations. So, we will consider array A to be sorted. We know that to make all the elements of A equal, it is always optimal to make those elements equal to the median of A.

Now, let’s denote the index of median of the array A as m . For now, let’s assume that to get the optimal answer we have to remove element whose index is less than or equal to m. We can clearly see here that removing the first element here is optimal because that element takes more operations than any other element on the left to get equal to the new median of A. Similar, arguments can be made for elements whose index is greater than or equal to m and we can see that removing the last element is optimal in this case.

So, we can try removing the first or last element after sorting the array and the answer will be the element whose removal produces less no. of operations.

SOLUTION:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

    long long fun(vector<int> v){
        int middle = v.size()/2;
        long long ans=0;
        for(auto u:v){
            ans+=abs(u-v[middle]);
        }
        return ans;
    }

    int solve(){
        
        int n;
        cin>>n;
        vector<int> v(n);
        for(int i=0;i<n;i++){
            cin>>v[i];
        }
        sort(v.begin(),v.end());

        vector<int> pref,suff;
        for(int i=0;i<n-1;i++){
            pref.push_back(v[i]);
        }
        for(int i=1;i<n;i++){
            suff.push_back(v[i]);
        }

        long long ans1=fun(pref),ans2=fun(suff);
        if(ans1<ans2){
            cout<<v[n-1]<<" "<<ans1;
        }
        else{
            cout<<v[0]<<" "<<ans2;
        }

        return 0;  
    }

    int main(){
        int t=1;
        cin>>t;
        while(t--){
            solve();
            cout<<"\n";
        }
    }
1 Like