L2-3.名人堂与代金券

题目内容

对于在中国大学MOOC(http://www.icourse163.org/) 学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。

输入格式

输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。

输出格式

首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

输入样例

10 80 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70

输出样例

360
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80
时间限制：150ms内存限制：65536kb

代码

解法一

用一个结构体来存姓名和成绩，再用自定义的比较函数sort一下。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct stu
{
    string name;
    int grade;
};
bool cmp(const stu& s1, const stu& s2)
{
    if(s1.grade != s2.grade)
        return s1.grade > s2.grade;
    else
        return s1.name < s2.name;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin.sync_with_stdio(false);
    int n, g, k;
    cin >> n >> g >> k;
    vector<stu> v;
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        string temp1;
        int temp2;
        cin >> temp1 >> temp2;
        stu temp;
        temp.name = temp1;
        temp.grade = temp2;
        v.push_back(temp);

        if(temp2 >= 60)
        {
            if(temp2 < g)
                ans += 20;
            else
                ans += 50;
        }
    }
    cout << ans << endl;

    int index = 1;
    int number = 1;
    sort(v.begin(), v.end(), cmp);
    vector<stu>::iterator t;
    ll flag = v[0].grade;
    for(t = v.begin(); t != v.end(); t++)
    {
        if(flag != (*t).grade)
        {
            flag = (*t).grade;
            index = number;
        }
        if(index > k)
            break;
        cout << index << " " << (*t).name << " " << (*t).grade << endl;
        number++;
    }
    return 0;
}

解法二

用一个map<string,name>来存name和grade,将map转存到vcetor到中进行排序。
比赛的时候好蠢好蠢的做法，后面会说。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

bool cmp (const pair<string,int>& a,const pair<string,int>& b)
{
    if(a.second!=b.second)
        return a.second>b.second;
    else
        return a.first<b.first;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin.sync_with_stdio(false);
    int n,g,k;
    cin>>n>>g>>k;
    map<string,int> m;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        string temp1;
        int temp2;
        cin>>temp1>>temp2;
        m.insert(pair<string,int>(temp1,temp2));
        if(temp2>=60)
        {
            if(temp2<g)
                ans+=20;
            else
                ans+=50;
        }
    }
    cout<<ans<<endl;

    vector<pair<string,int>> mm(m.begin(),m.end());//map转存至vector
    sort(mm.begin(),mm.end(),cmp);

    int index=1;
    int number=1;
    vector<pair<string,int>>::iterator t=mm.begin();
    ll flag=(*t).second;
    for(t=mm.begin();t!=mm.end();t++)
    {
        if(flag!=(*t).second)
        {
            flag=(*t).second;
            index=number;
        }
        if(index>k)
            break;
        cout<<index<<" "<<(*t).first<<" "<<(*t).second<<endl;
        number++;
    }
    return 0;
}

总结

比赛的时候没看清题意，上来就直接一个map，快写完了的时候才发现不对，然后就突发奇想的对map进行sort，但是编译的时候比较函数那一行一直报错。我到现在都不清楚为什么比赛的时候要一直死磕对map按照value进行sort，就是懒得改成结构体加vector，结果直到比赛结束前几分钟才开始改，虽然改完了可惜没时间交了。
回到宿舍终于在网上找到了对map进行sort的方法：将map转存至vector中，然后sort。vector<pair<string,int>> mm(m.begin(),m.end());但是还是用结构体加vector方便啊。
还是自己菜啊…….

注意：STL库中的sort函数只能对线性存储的对象进行排序,如:vector、array、list、deque,不能对集合容器进行排序,如:set、map;

参考博客:C++ STL中Map的按Key排序和按Value排序