Codeforces Round #629 (Div. 3) F. Make k Equal （技巧暴力，类前缀和，思维，数学）

F. Make k Equal

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given the array aa consisting of nn elements and the integer k≤nk≤n.

You want to obtain at least kk equal elements in the array aa. In one move, you can make one of the following two operations:

• Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of aa is mnmn then you choose such index ii that ai=mnai=mn and set ai:=ai+1ai:=ai+1);
• take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of aa is mxmx then you choose such index ii that ai=mxai=mx and set ai:=ai−1ai:=ai−1).

Your task is to calculate the minimum number of moves required to obtain at least kk equal elements in the array.

Input

The first line of the input contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of elements in aa and the required number of equal elements.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the ii-th element of aa.

Output

Print one integer — the minimum number of moves required to obtain at least kk equal elements in the array.

Examples

input

Copy

6 5
1 2 2 4 2 3

output

Copy

3

input

Copy

7 5
3 3 2 1 1 1 3

output

Copy

4

题意：输入n，m，然后给你n个数，每次可以让这些数最大值减一或者让最大值加一，问最少进行多少次操作变成m个相同的数

这道题其实没有那么难，我们可以一步步分析：

首先，大体思路是我们可以枚举每一个数假设它为最后变成m个相同的数，求出变出来的操作最后每个数都有一个操作数，取最小就是答案了，那么接着我们就要研究特定的数，怎么求出最少要进行多少次操作才能至少有另外的m-1个数和它一样呢？

我们要明白一件事，如果我们的目标是数列中的某个数x，那么我们必须把比它小的所有数都变成x-1才行，当然啦，你也可以把比它大的数全部变成x+1，这一定是必要条件，才能继续操作，所以首先我们要排个序

为什么要变成x+1或者x-1，因为肯定不是直接变成x啊，你要多少变成x是根据你的m来的鸭

那么两个关键指标就出现了，我们能获取比x小的数（让它变成x）有多少？能获取比x大的数（让它变成x）有多少？

设第一个为a，第二个为b，再定义我们需要的数为need=n-cnt[x],cnt[x]为出现的次数，这是免费的，不需要任何操作就已经有了，我们

不用在动它们

当然了，a+b一定>=need，有以下三种情况:

a<need,b<need(那么就是两种代价相加)

a>need,b<need(那么就是所有数来源都是比x小的数，算这部分代价就好）

a<need,b>need(那么就是所有数来源都是比x大的数，算这部分代价就好）

思路讲完了，相信你也会写代码了~

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define lb(x) (x&(-x))
const ll inf=1e18;
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
ll n,k,a[200005],pre[200005],suf[200005];
map<ll,ll>cnt;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;	
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
	for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
	ll minn=inf,flag=0;
	for(int i=1;i<=n;i++)
	{
		if(cnt[a[i]]>=k)
		{
			flag=1;
			break;
		}
		ll need=k-cnt[a[i]];
		ll cost1=(a[i]-1)*(i-1)-pre[i-1],cost2=suf[i+cnt[a[i]]]-(a[i]+1)*(n-i-cnt[a[i]]+1);
		
		ll buyi=i-1,buer=n-i-cnt[a[i]]+1;
		if(buyi>=need&&buer>=need)minn=min(minn,min(cost1,cost2)+need);
		else if(buyi>=need&&buer<need)minn=min(minn,cost1+need);
		else if(buyi<need&&buer>=need)minn=min(minn,cost2+need);
		else minn=min(cost1+cost2+need,minn);
		//cout<<need<<" "<<cnt[a[i]]<<" "<<cost1<<" "<<cost2<<" "<<minn<<endl;
		i+=cnt[a[i]]-1;
	}
	if(flag)cout<<0<<endl;
	else cout<<minn<<endl;
    return 0;
    
}