Codeforces Round #629 (Div. 3) F. Make k Equal

发表于 分类于

链接

https://codeforces.com/contest/1328/problem/F

题意

操作一：使最小的数加一。
操作二：使最大的数减一。

求最小操作数使序列中有 $k$ 个相同的数。

思路

排序后，枚举每个不同的数。

操作只有三种 Case：

  • 只操作比当前小的数。
  • 只操作比当前大的数。
  • 操作一部分比当前小的数，操作一部分比当前大的数。

易发现不管是操作小的数还是操作大的数，我们都需要将一边的所有数都先操作为与当前数相差为 $1$ 的数才能增加当前数个数，用前缀和预处理。

代码

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
43
44
45
46
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=2e5+5;
int n,k;
LL a[N],tot[N],sum[N],c[N],d[N];
vector<LL> b;
int main() {
    //freopen("E:/OneDrive/IO/in.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        b.PB(a[i]);
    }
    sort(ALL(b));
    b.resize(unique(ALL(b))-b.begin());
    for(int i=1;i<=n;i++) ++tot[lower_bound(ALL(b),a[i])-b.begin()];
    sum[0]=tot[0];
    for(int i=1;i<SZ(b);i++) sum[i]=tot[i]+sum[i-1];
    for(int i=1;i<SZ(b);i++) c[i]=c[i-1]+sum[i-1]*(b[i]-b[i-1]);
    for(int i=SZ(b)-2;i>=0;i--) d[i]=d[i+1]+(sum[SZ(b)-1]-sum[i])*(b[i+1]-b[i]);
    LL mn=0x3f3f3f3f3f3f3f3f;
    for(int i=0;i<SZ(b);i++) {
        if(tot[i]>=k) {puts("0");return 0;}
        LL sum1=0,sum2=0;
        if(i-1>=0) sum1=c[i-1]+sum[i-1]*(b[i]-b[i-1]-1);
        if(i+1<SZ(b)) sum2=d[i+1]+(sum[SZ(b)-1]-sum[i])*(b[i+1]-b[i]-1);
        if(i-1>=0&&sum[i-1]+tot[i]>=k) mn=min(mn,sum1+k-tot[i]);
        if(sum[SZ(b)-1]-sum[i]+tot[i]>=k) mn=min(mn,sum2+k-tot[i]);
        mn=min(mn,sum1+sum2+k-tot[i]);
    }
    printf("%lld\n",mn);
    return 0;
}