PROBLEM LINK:
Practice
Tester: Aman Nautiyal
Editorialist: Aman Nautiyal
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Binary search on answer, greedy.
PROBLEM:
You have n gift packets of candies and you want to give all of them to children. Of course, you don’t want to hurt anyone, so you want to minimize the difference between candies that any two children will get. In one move you can take a gift packet , and take a single candy from it and put it in any other gift packet.
You want to find the minimum difference of candies that any two children will get using not more than k moves.
EXPLANATION:
Key observation is that we can apply operations separately this means first we will apply all decrease operations, and after that apply all increase operations or vice versa. We will use following algorithm.
We have to apply operations at most k times, add one to minimum number in array. We will simply binary search over minimum value after applying k operation.
Let’s see how to check if minimum will be great or equal to p. If
1<=i<=n Σ max(0,p-c[i])
, is less or equal to k then we can increase all elements to at least p. In this way we can find what will be minimum value after k operations.
Let’s say this minimum value is p. After we find it we will increase all numbers less than p to p. But there may be some operations we still didn’t apply yet, this number can be at most (n - 1),
otherwise minimum would be greater than m because we can increase all numbers equal to m by one with this number of increases.
Since minimum has to be same we just have to increase some elements in our array that equal to m. We will use same algorithm for decreasing operations.
Final answer: max_element - min_element after k operations.
Time complexity : O(N*logK)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long int
using namespace std;
const int N=5e5+5;
int a[N];
void solve(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
int L=1,U=1e9,min_element;
while(L<=U){
int m=(L+U)/2;
int t=0,z=0;
for(int i=0;i<n;i++){
if(a[i]<m){
t+=m-a[i];
}
else{
z+=a[i]-m;
}
}
if(t<=k && z>=t){ // if it is possible to make min element = m
L=m+1;
min_element=m;
}
else{
U=m-1;
}
}
L=1,U=1e9;
int max_element;
while(L<=U){
int m=(L+U)/2;
int t=0,z=0;
for(int i=0;i<n;i++){
if(a[i]<m){
t+=m-a[i];
}
else{
z+=a[i]-m;
}
}
if(z <= k && t>=z){
U=m-1;
max_element=m;
}
else{
L=m+1;
}
}
cout<<max_element-min_element;
}
signed main()
{
IOS;
int T=1;
// cin>>T;
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}