[cf] 797 div3 E. Price Maximization

Preface

Portal :
The question :
Given $n$ Parcel , Two parcels merged , Its value is the sum of two numbers except k, Find the maximum value after merging all packages

Ideas :
Consider not merging first , So the value of each package is $a[i]/k$

Then we greedily consider merging , Take the rest of these packages and put them into the bucket , Find the double pointer Can match and Own and own

code :

int a[N],cnt[N];
int n,k;

void solve(){
    
	ll res = 0;
	
	cin>>n>>k;
	
	for(int i=1;i<=n;i++){
    
		cin>>a[i];
		cnt[a[i]%k]++;// Barrel storage 
		res += a[i]/k;
	}
	
	int sum = 0;
	for(int i=1 , j = k-1 ;i<=j ;i ++ ,j  -- ){
    
		sum += cnt[j];
		if(i == j) break;
		
		// Bound by the less 
		int t = min(sum,cnt[i]);
		
		res +=t;
		sum -=t;
	}
	// /2 Because   Two in each group 
	cout<<res+sum/2<<endl;
	
	for(int i=1;i<=n;i++) cnt[a[i]%k] -- ;// Empty 
}

int main(){
    
    int t;cin>>t;while(t--)
    solve();
    return 0 ;
}