https://codeforces.com/contest/1490/problem/F
題意:問最小洗掉多少個數字使得剩下的數字出現次數都一樣，
思路:
開始就是暴力列舉剩下一個次數，這樣肯定要用一些東西優化，
預處理一下某個次數有多少個種類的數字出現過，然后列舉的時候就可以O1洗掉，在列舉的次數后面的數由于次數比他多，不能全刪，轉化一下，先全洗掉，再加上多洗掉的，多洗掉的預處理一下某個次數有幾個種類的數的后綴，
update:以后cf比賽還是不用unordered_map了，改成map就好了
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+100;
typedef int LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
unordered_map<LL,LL>map1,map2,v;
LL a[maxn],sum[maxn],suf[maxn],p[maxn];
void init(LL n){
map1.clear();map2.clear();v.clear();
for(LL i=0;i<n+10;i++) a[i]=sum[i]=suf[i]=p[i]=0;
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL t;cin>>t;
while(t--){
LL n;cin>>n;
init(n);
LL maxv=0;
for(LL i=1;i<=n;i++){
cin>>a[i];
map1[a[i]]++;
maxv=max(maxv,map1[a[i]]);
}
for(LL i=1;i<=n;i++){
if(map2.count(a[i])) continue;
map2[a[i]]=1;
v[map1[a[i]]]++;///統計出現某次數一共有多少數字
}
for(LL i=1;i<=maxv;i++) sum[i]=sum[i-1]+v[i]*i;///累加數字總數
for(LL i=maxv;i>=1;i--) suf[i]=suf[i+1]+v[i]*i;///后綴數字總數
for(LL i=maxv;i>=1;i--) p[i]=p[i+1]+v[i];///后綴數字種類和
LL ans=0x3f3f3f3f;
for(LL i=1;i<=maxv;i++){
ans=min(ans,sum[i-1]+(suf[i+1]-p[i+1]*i));///前面數字都歸0,后面數字先歸0，再加上變成和當前次數一樣的數目
}
cout<<ans<<"\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/260627.html
標籤：其他