L2-021 点赞狂魔 (25分)

看起来就是一个很普通的排序

知识扩充：部分排序Partial Sor

t对于部分排序，有一个特殊的算法 partial_sort()，它需要 3 个随机访问迭代器作为参数。如果这个函数的参数是 first、second 和 last，那么这个算法会被应用到 [first，last) 这个范围内的元素上。执行这个算法后，[first，second) 会包含降序序列 [first，last) 中最小的 second-first 个元素（默认升序），然后我们可以用cmp

int nn = min(n, 3);
partial_sort(ans.begin(),ans.begin() + nn, ans.end(), cmp);
for(int i = 0; i < nn; i++) {
     if(i != 0) cout << " ";
     cout << ans[i].name;
}

partial_sort的原理：部分排序的原型出现在STL的算法库里面，根据其所描述的代码，很容易可以看出来partial_sort是借用了堆排序的思想来作为底层排序实现的。对于该算法的原理这样描述。假设我们有n个元素序列，需要找到其中最小的m个元素，m<=n时。 先界定区间[first, m) 然后对该区间使用make_heap()来组织成一个大顶堆。然后遍历剩余区间[m,
 last)中的元素， 剩余区间的每个元素均与大顶堆的堆顶元素进行比较（大顶堆的堆顶元素为最大元素，该元素为第一个元素，很容易获得），若堆顶元素较小，交换堆顶元素和遍历得到的元素值，重新调整该大顶堆以维持该堆为大顶堆。遍历结束后，[first, m)区间内的元素便是排名在前的m个元素，在对该堆做一次堆排序便可得到最好的结果。
————————————————
版权声明：「dreamhougf」

#include<bits/stdc++.h>
using namespace std;
// 如果有并列，则输出标签出现次数平均值最小的那个
struct node{
    string name;
    double avg;
    int size;
}people[110];
bool cmp(node a,node b){
    if(a.size!=b.size) return a.size>b.size;
    else return a.avg<b.avg;
}
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        string name;int k;set<int> tag;
        cin>>name>>k;
        for(int j=0;j<k;j++){
            int x;cin>>x;
            tag.insert(x);
        }
        people[i].name=name;people[i].size=tag.size();
        people[i].avg=1.0*k/people[i].size;
    }
    sort(people,people+n,cmp);
    for(int i=1;i<=3;i++){
        if(i!=1) cout<<" ";
        if(n<i) cout<<"-";
        else cout<<people[i-1].name;
    }
    return 0;
}