CF1328F

看了题，写了一发，发现假了，赶紧退赛

所以咕咕咕

早上起来填坑，发现我的思路并没有假。。。

回到正题，我们发现每次操作的数只能是最大或最小。显然有个结论是最后相等的(k)个数一定是本身存在于(a[i])的数(如果大向小靠近，不会变成更小，反之亦然)。然后，要使一个数变成(a[i])，必须把其他的一堆数全部变成(a[i] - 1) 或 (a[i] + 1)。最后分三种情况讨论一下就好。

PS : 记得离散化。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define N 700005
map <int, int> used;

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

ll sum[N], suf[N];

int main()
{
	scanf("%d%d", &n, &k);
	int tmp = 0;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		used[a[i]] = 1;
		b[++tmp] = a[i], b[++tmp] = a[i] - 1, b[++tmp] = a[i] + 1;
	}
	sort(b + 1, b + tmp + 1);
	int num = unique(b + 1, b + tmp + 1) - b - 1;
	for(int i = 1; i <= n; i++)
	{
		int x = lower_bound(b + 1, b + num + 1, a[i]) - b;
		cnt[x]++;
		if(cnt[x] >= k) 
		{
			cout << 0 << endl;
			return 0;
		}
	}
	int c = 0;
	for(int i = 1; i <= num; i++)
	{
		if(i > 1) sum[i] = sum[i - 1] + 1ll * c * (b[i - 1] - b[i - 2]);
		c  += cnt[i - 1];
		// cout << b[i] << ' ' << sum[i] << endl;
	}
	c = 0;
	ll ans = LLONG_MAX;
	for(int i = 1; i <= num; i++)
	{
		c += cnt[i];
		if(c < k) continue;
		if(used[b[i]]) ans = min(ans, sum[i] + 1ll * (k - cnt[i]));
	}
	c = 0;
	for(int i = num; i >= 1; i--)
	{
		if(i < num) suf[i] = suf[i + 1] + 1ll * c * (b[i + 2] - b[i + 1]);
		c += cnt[i + 1];
	}
	c = 0;
	// for(int i = 1; i <= num; i++)
	// 	cout << b[i]  << ' ' << sum[i] << ' ' << suf[i] << endl;
	for(int i = num; i >= 1; i--)
	{
		if(used[b[i]]) ans = min(ans, sum[i] + suf[i] + 1ll * (k - cnt[i]));
		c += cnt[i];
		if(c < k) continue;
		if(used[b[i]]) ans = min(ans, suf[i] + 1ll * (k - cnt[i]));
	}
	cout << ans << endl;
	return 0;
}