CF1490F题解

二gou子 · 2021-02-17 12:00:50 · 题解

题目大意

给出一个数列，将每一个数的出现次数变为0或C，其中C是一个任意正整数，每次操作可以删除一个数，问最少操作次数。

思路

首先肯定要开桶统计每个数的个数，但是注意到数列内的数范围较大，所以要先进行离散化。离散化之后开桶记录每个数的出现次数，则次数又构成了一个新的序列。这样问题就转化为：给出一个序列，对于序列中的每一个数，如果大于等于C，就变成C；反之，变成0。每次操作可以将任意一个数减1，求最小操作数。

我们这样思考：首先假设我们把所有的数都变成0，那其实也就是删掉原数列内的所有数，操作次数就是n。然后枚举C，小于C的数还是变成0不变，而大于等于C的数就要变成C。这些数原先要变成0，但是现在变成C。相当于在n的基础上，节省了大于等于C的数的个数*C次操作。这样我们只需要枚举一下C，O(1)更新一下答案，这个题就做完了。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
int t,n,maxx,p;
int a[2000005],b[2000005],sum[2000005];
ll summ,ans;
void lisan(){
    for(int i=1;i<=n;i++){
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    p=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+p,a[i])-b;
    }
}
int main()
{
    scanf("%d",&t);
    while(t--){
        summ=0,maxx=0,ans=1000000000000000;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        lisan();
        for(int i=1;i<=n;i++){
            sum[a[i]]++;
            maxx=max(maxx,sum[a[i]]);
//          printf("%d ",a[i]);
        }
        sort(sum+1,sum+1+p);
//      for(int i=1;i<=p;i++){
//          printf("%d ",sum[i]);
//      }
//      printf("\n");
//      printf("\n");
        for(int i=1;i<=p;i++){
            ans=min(ans,n-1ll*sum[i]*(p-i+1));
            while(sum[i]==sum[i+1]) i++;
        }
        printf("%d\n",ans);
        for(int i=1;i<=p;i++){
            sum[i]=0;
        }
    }
    return 0;
}

（由于Div3时间较紧，代码比较混乱，但思路才是主要的）