牛客练习赛15 B 沃老师学生的成绩

Description:

第一次期中考终于结束啦！沃老师是个语文老师，他在评学生的作文成绩时，给每位学生的分数都是一个小于10的非负小数。

Amy 8.999999999999999999999999999999999999999990000
Bob 8.9999999999999999999999999999999999999999800
Cat 8.9999999999999999999999999999999999999999899999999

沃老师并不会告诉大家分数的排名，但学生间竞争激烈，大家都想知道自己的作文成绩在班上的排名。
但由于作文分数的小数部分可能超级长，难以用肉眼比较两个数的大小关系，请你帮忙写个程序，把所有学生按照作文分数排序吧〜

Input:

输入共有N + 1行。
第一行有一个正整数N，代表班上有几个人。
接下来N行中的第i行，包含一个字符串namei，以及一个小数scorei，分别代表第i个人的名字以及第i个人的作文得分。

Output:

输出总共N行，每行由一个名字和一个小数构成，第i行代表着分数第i高的人的名字以及他的作文得分，代表作文得分的小数必须和输入一模一样，也就是原本末尾有多少零，输出也要有相同数量的零。
若分数相同，则名字字典序比较小的放在前面。

Sample Input:

3
Amy 8.999999999999999999999999999999999999999990000
Bob 8.9999999999999999999999999999999999999999800
Cat 8.9999999999999999999999999999999999999999899999999

Sample Output:

Amy 8.999999999999999999999999999999999999999990000
Cat 8.9999999999999999999999999999999999999999899999999
Bob 8.9999999999999999999999999999999999999999800

Sample Input:

6
Aa1 3.
Bb2 2.
Cc3 1.
a 5.
A 5.0
9 5.00

Sample Output:

9 5.00
A 5.0
a 5.
Aa1 3.
Bb2 2.
Cc3 1.

Sample Input:

10
peter50216 5.0216
kelvin 9.9999999990
seanwu 9.999999999
pp5438 5.438
csferng1021 1.021
tmt514 5.140
dreamoon 0.00000000
shik 9.999999999
l521530 5.21530
coquelicot 9.999999999000000000

Sample Output:

coquelicot 9.999999999000000000
kelvin 9.9999999990
seanwu 9.999999999
shik 9.999999999
pp5438 5.438
l521530 5.21530
tmt514 5.140
peter50216 5.0216
csferng1021 1.021
dreamoon 0.00000000

题目链接

由于小数点后面有很多位，所以分数一定要用字符串储存，按照规则进行结构体排序，这里用sort(,cmp)会超时(也可能是我的排序算法太渣)，但是把sort换成stable_sort就可以过(我也不知道为什么，看别人代码是这么过的)，其实也可以用优先队列按照排序规则进行排序。

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

struct ac {
    string name;
    string grade;
    int len;
    bool operator < (const ac &a) const {
        if (a.grade[0] != grade[0]) {
            return a.grade[0] > grade[0];
        }
        int sma = a.len < len ? a.len : len, cnt = 2;
        while (cnt < sma) {
            if (a.grade[cnt] != grade[cnt]) {
                return a.grade[cnt] > grade[cnt];
            }
            cnt++;
        }
        if (a.len != len) {
            return a.len > len;
        }
        return a.name < name;
    }
}people[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    priority_queue<ac> que;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> people[i].name >> people[i].grade;
        people[i].len = people[i].grade.length();
        for (int j = people[i].len - 1; j >= 0; --j) {
            if (people[i].grade[j] == '0') {
                people[i].len--;
            }
            else {
                break;
            }
        }
        que.push(people[i]);
    }
    for (int i = 0; i < n; ++i) {
        ac output;
        output = que.top();
        que.pop();
        cout << output.name << " " << output.grade << endl;
    }
    return 0;
}