CF1328F 题解
$\text{Descrption}$
给定 $n$ 个数，每次可以将最小的数加一或者将最大的数减一，问要有 $k$ 个相等的数最少需要多少此操作。
$n,k\le 2\times 10^5,a_i\le 10^9$。
$\text{Solution}$
首先容易发现排序不影响答案。
然后考虑把序列分为若干个段，每段内数都相同，不同的段内数不相同。
我们想要枚举最后 $k$ 个相同的数的数值，但是直接枚举复杂度太高。我们发现，若这个数值在序列中不存在，它一定不是最优的。所以我们直接枚举每个段计算答案即可。
$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
#define REG register
using namespace std;
typedef long long ll;
const int Maxn=200005;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
int n,k;
int a[Maxn];
ll pre[Maxn],suf[Maxn];
int l[Maxn],r[Maxn],tot;
inline void Work(){
read(n),read(k);
for(REG int i=1;i<=n;++i) read(a[i]);
sort(a+1,a+n+1);
for(REG int i=1;i<=n;++i) pre[i]=pre[i-1]+a[i];
for(REG int i=n;i;--i) suf[i]=suf[i+1]+a[i];
for(REG int i=1;i<=n;++i)
if(a[i]==a[i-1]) ++r[tot];
else ++tot,l[tot]=r[tot]=i;
ll ans=50000000000000000ll;
for(REG int i=1;i<=tot;++i){
int len=r[i]-l[i]+1;
if(len>=k) {puts("0");return;}
if(r[i]>=k) ans=min(ans,1ll*(l[i]-1)*(a[l[i]]-1)-pre[l[i]-1]+k-len);
if(n-l[i]+1>=k) ans=min(ans,suf[r[i]+1]-1ll*(n-r[i])*(a[l[i]]+1)+k-len);
if(r[i]<k&&n-l[i]+1<k) ans=min(ans,1ll*(a[l[i]]-1)*(l[i]-1)+suf[r[i]+1]-1ll*(a[l[i]]+1)*(n-r[i])-pre[l[i]-1]+k-len);
}
printf("%lld\n",ans);
getchar(),getchar();
}
int main(){Work();}
|
