Different approach to solve "make all equal"

help
, ,
1

I used the method of difference array to solve the problem - Problem link

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main() {
	// your code goes here
	long t;
	cin>>t;
	while(t--){
	    int n;cin>>n;
	    int m;cin>>m;
        vector<int>a(n);
        vector<int>dif(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
            
        }
        sort(a.begin(),a.end());
        dif[0]=a[0];
        for(int i=1;i<n;i++){
           
            
            dif[i]=a[i]-a[i-1];
        }
        
        
        int idx=n-1;
        int op=0;
        for(;idx>=0;idx--){
            
            if(dif[idx]==0){continue;}
            else{
            op+=dif[idx];
            
            if((idx-m)>=0){
            dif[idx-m]+=dif[idx];
                }else{
                dif[0]+=dif[idx];
            }
            dif[idx]=0;
            }
        
        }
        cout<<op-a[n-1]<<endl;
	}
	return 0;
}

it is giving the wrong answer. please help

2

Hey @shreyan_zz1 Your logic is wrong, you should use summation of differences from maximum element not prefix differences.
You should return maximum of (difference between maximum and minimum element) and (ceiling value of summation/k).

Here is my detailed explaination with solution:
https://www.codechef.com/viewsolution/1035944654

1 Like