C- Set or Decrease Codeforces Educational Round 120
Approach-
Since, we have been asked to find the minimum number of operations, the first thought that should come to our mind should be of using Binary Search. And yes, half of the task is done.
But how to make the check function for binary search. So, lets say we have some operations available to us (totaloperations), now from this we can do two types of operations, be it the subtract operation (ai=ai-1) or the replace operation (aj=ai). So, we should check for every possible value between 0 and maximum possible replaceable elements i.e n-1 using a for loop. So, for each value (replace) from 0 to min( totaloperations, n-1) we get subtracted value as totaloperations-replace. For these two values, check if the current sum of elements is <= k or not. Prefix Sum is used to reduce the time complexity for calculating the sum of array elements.
Below is the detailed code in C++ exactly matching with the explanation above.
Code-
#define ll long long
ll check(ll a[], ll prefix[], ll totaloperations, ll k, ll n)
{
ll totalsum;
for(ll replace=0;replace<=min(n-1,m);replace++)
{
ll subtract=totaloperations-replace;
if(replace==0)
totalsum=p[n-1]-subtract;
else
totalsum=(replace)*(a[0]-subtract)+p[n-1-replace]-subtract;
if(totalsum<=k)
return 1;
}
return 0;
}
int main()
{
ll testcase=1;
cin >> testcase;
for(ll i=0;i<testcase;i++)
{
ll n, k;
cin>>n>>k;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
ll prefix[n];
prefix[0]=a[0];
for(ll i=1;i<n;i++)
{
prefix[i]=prefix[i-1]+a[i];
}
ll s=0, e=1e18;
ll ans=-1;
while(s<=e)
{
ll mid=s+(e-s)/2;
if(check(a,p,mid,k,n)==1)
{
ans=mid;
e=mid-1;
}
else
{
s=mid+1;
}
}
cout<<ans<<endl;
}
}
Other Problems from this Contest-
Disclaimer- Everything is published after the actual contest gets over.
Comments