|
|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
×
- #include<bits/stdc++.h>
- // #define int long long
- #define INF 0x3f3f3f3f3f
- #define endl '\n'
- using namespace std;
- typedef pair<int,int>pii;
- void solve()
- {
- int n;
- cin>>n;
- vector<int>a(n);
- map<int,int>mp;
- vector<int>cnt;
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- mp[a[i]]++;
- }
- for(auto [a,b]:mp)
- {
- cnt.push_back(b);
- }
- sort(cnt.begin(),cnt.end());
- vector<int>sum(cnt.size());
- sum[0]=cnt[0];
- for(int i=1;i<n;i++)
- {
- sum[i]=sum[i-1]+cnt[i];
- }
- int ans=INF;
- for(int i=0;i<=n;i++) //i最小为0次,最大为n次
- {
- // 二分找那个点
- int pos =lower_bound(cnt.begin(),cnt.end(),i)-cnt.begin(); //找到大于等于x的位置
- int cost =0;
- cost =sum[pos-1]+sum.back()-sum[pos-1]-(cnt.size()-pos)*i; // pos后面那个要减去的数
- ans=min(cost,ans);
- }
- cout<<ans<<endl;
- }
- signed main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int t;
- cin>>t;
- while(t--)
- {
- solve();
- }
- }
复制代码 |
|