[C++知识库]Codeforces Round #773 (Div. 2) B. Power Walking

大佬讲解

Sam有n个技能分给k个人。
对于1 1 2 2 3 3来说
有三种不同的技能，那么在前三次可以这样分配：
{1 1 2 2 3 3}
{1 1 2 2 } {3 3}
{1 1} {2 2} {3 3}
那么在之后的分配中，就需要去将相同的技能分给别的小朋友，如果一个集合中的技能有两个以上，那么是可以分出去的，如果一个集合中的技能只有一个，此时已经无法再分。

用优先队列（小根堆）存储每个数出现的次数，若Sam有k个不同的技能，那么在前k次的时候，结果一定是k。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int t, n, a[N];

void solve()
{
    cin >> n;
    map<int,int> cnt;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    int res = 0, k = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        cin >> a[i];
        if(!cnt.count(a[i])) res ++;
        cnt[a[i]] ++;
    }
    k = res;
    for(auto& x : cnt)
    {
        q.push({x.second, x.first});
    }
    for(int i = 1; i <= n; i ++)
    {
        if(i <= k)
        {
            cout << k << ' ';
            continue;
        }
        while(q.top().first <= 1) q.pop();
        PII tt = q.top();
        q.pop();
        tt.first --;
        if(tt.first != 0)
        {
            res ++;
        }
        if(tt.first)
            q.push(tt);
        cout << res << ' ';
    }
    cout << endl;
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}