PTA乙级题 1085. PAT单位排行 (25)

【题目链接】

自己写的代码最后两个测试点5分运行超时，题目给的数据量是真的大。

#include<iostream>
#include<string>
#include<map>
#include<cctype>
#include<cmath>
#include<algorithm>
using namespace std;
typedef struct
{
    string type;
    double score;
    string name;
}NODE;
typedef struct
{
    int flag;
    string school;
    double data;
    int count;
}node;
int cmp(node a, node b)
{
    if (a.data != b.data)
        return a.data > b.data;
    if (a.count != b.count)
        return a.count < b.count;
    return a.school < b.school;
}
int main()
{
    map<string, int>M;
    int i, n, x = 1;
    cin >> n;
    NODE stu[n+1];
    node sch[n+1];
    for (i = 0; i<n; i++)
    {
        cin >> stu[i].type >> stu[i].score >> stu[i].name;
        for (size_t j = 0; j<stu[i].name.size(); j++)
            stu[i].name[j] = tolower(stu[i].name[j]);
        if (M[stu[i].name] == 0)
        {
            M[stu[i].name] = x;
            sch[x].school = stu[i].name;
            sch[x].count = 1;
            switch (stu[i].type[0])
            {
            case 'A':
                sch[x].data = stu[i].score;
                break;
            case 'B':
                sch[x].data = (int)(stu[i].score / 1.5);
                break;
            case 'T':
                sch[x].data = (int)(stu[i].score*1.5);
                break;
            }
            x++;
        }
        else
        {
            sch[M[stu[i].name]].count++;
            switch (stu[i].type[0])
            {
            case 'A':
                sch[M[stu[i].name]].data += stu[i].score;
                break;
            case 'B':
                sch[M[stu[i].name]].data += (int)(stu[i].score / 1.5);
                break;
            case 'T':
                sch[M[stu[i].name]].data += (int)(stu[i].score*1.5);
                break;
            }
        }
    }
    sort(sch + 1, sch + x, cmp);
    cout << x - 1 << endl;
    for (i = 1; i < x; i++)
    {
        if (i == 1)
            sch[i].flag = i;
        else
        {
            if (sch[i].data == sch[i - 1].data)
                sch[i].flag = sch[i - 1].flag;
            else
                sch[i].flag = i;
        }
        cout << sch[i].flag << " " << sch[i].school << " ";
        printf("%d", (int )(sch[i].data));
        cout << " " << sch[i].count << endl;
    }
}

水平有限，转一下柳婼小姐姐的AC代码。

#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>
#include <map>
using namespace std;
struct node {
    string school;
    int tws, ns;
};
bool cmp(node a, node b) {
    if (a.tws != b.tws)
        return a.tws > b.tws;
    else if (a.ns != b.ns)
        return a.ns < b.ns;
    else
        return a.school < b.school;
}
int main() {
    int n;
    scanf("%d", &n);
    map<string, int> cnt;
    map<string, double> sum;
    for (int i = 0; i < n; i++) {
        string id, school;
        cin >> id;
        double score;
        scanf("%lf", &score);
        cin >> school;
        for (int j = 0; j < school.length(); j++)
            school[j] = tolower(school[j]);
        if (id[0] == 'B')
            score = score / 1.5;
        else if (id[0] == 'T')
            score = score * 1.5;
        sum[school] += score;
        cnt[school]++;
    }
    vector<node> ans;
    for (auto it = cnt.begin(); it != cnt.end(); it++)
        ans.push_back(node{it->first, (int)sum[it->first], cnt[it->first]});
    sort(ans.begin(), ans.end(), cmp);
    int rank = 0, pres = -1;
    printf("%d\n", (int)ans.size());
    for (int i = 0; i < ans.size(); i++) {
        if (pres != ans[i].tws) rank = i + 1;
        pres = ans[i].tws;
        printf("%d ", rank);
        cout << ans[i].school;
        printf(" %d %d\n", ans[i].tws, ans[i].ns);
    }
    return 0;
}