LT18-Editorial

editorial
,
1

Problem Link

Loop Through

Author:pskalbhav1

Difficulty

HARD

Prerequisites

Greedy

Problem Statement

You visit an ancient hanging bridge consisting of n planks, but they are broken or disoriented and you want to correct them. You want to obtain at least k equally placed planks in the bridge.

In one move, you can make one of the following two operations:
*Take one of the minimum planks of the bridge and shift it up by one cm.
*Take one of the maximum planks of the bridge and shift it down by one cm.

Your task is to calculate the minimum number of moves required to obtain at least k equally placed planks in the bridge [k≤n]

Approach

This problem is just all about the implementation. Firstly, let's sort the initial values and compress them to pairs (i,cnt[val]), where cnt[val] is the number of elements val. The first observation is pretty standard and easy: some equal elements will remain unchanged. So let's iterate over all elements valval in some order and suppose that all elements valval will remain unchanged. Firstly, we need need=max(0,k−cnt[val]) elements which we should obtain by some moves. The second observation is that we first need to take elements from one end (only less or only greater) and only then from the other (if needed).

Consider the case when we first take less elements. The other case is almost symmetric.

Let needl=min(need,prefcntprv) be the number of less than valval which we need to increase to valval. If needl=0needl=0 then skip the following step. Otherwise, let prefcnti be the number of elements less than or equal to i, prefsumi be the sum of all elements less than or equal to i and prv be the previous value (the maximum value less than valval). Then we need to increase all elements less than or equal to prv at least to the value val−1. It costs (val−1)⋅prefcntprv−prefsumprv moves. And then we need needl moves to increase needln elements to valval.

And let needr=max(0,need−needl) be the number of elements greater than valval which we need to decrease to valval if we increased needl elements already. If needr=0 then skip the following step. Otherwise, let sufcnti be the number of elements greater than or equal to i, prefsumi be the sum of all elements greater than or equal to i and nxt be the next value (the minimum value greater than valval). Then we need to decrease all elements greater than or equal to prvprv at least to the value val+1. It costs sufsumnxt−(val+1)⋅sufcntnxt moves. And then we need needr moves to decrease needr elements to valval.

So we can update the answer with the sum of values described above and proceed to the next value. Arrays prefcnt, sufcnt, prefsum, sufsum are just simple prefix and suffix sums which can be calculated in O(n) using very standard and easy dynamic programming. Don’t forget about the overflow.

Total time complexity: O(nlogn) because of sorting.

Solution

#include<bits/stdc++.h>
using namespace std;
long long n,k,i,j,m,a[200008],c[200008];
int main()
{
    for(scanf("%I64d%I64d",&n,&k); i++<n; scanf("%I64d",a+i));
    for(sort(a+1,a+n+1),i=0; i++<n; c[i]=c[i-1]+a[i]);
    for(i=n-k; i++<n; m+=a[i]-a[n+1-k]);
    for(i=n+1-k; a[n+1-k]==a[--i]; --m);
    for(i=0; i++<k; j+=a[k]-a[i]);
    for(i=k; a[k]==a[++i]; --j);
    for(j<m?m=j:0,i=1; i<=n&&0<m; j<i+k? m=min(m,c[n]-(c[i]<<1)+a[i]*(i+i-n)+k-n):m=0,i=j)
    for(j=i; a[i]==a[++j];);
    printf("%I64d\n",m<0?0:m),exit(0);

}