东方博宜1542 - 小X算排名

题目描述

小 X 很关心自己在学校的表现。
班主任手上有一本“个人得分记录本”，如果一位同学表现好就会加分，表现差则会扣分。学期结束，每位同学都得知了自己的个人得分。小 X 想知道其他同学情况如何，但由于排名不公布，他只好一个个去问班里的其他同学。
现在，小 X 手上有班里共 N 位同学的个人得分，他想知道每位同学的排名 （得分相同则排名相同，见样例），可并不知道该如何计算，希望你帮帮他。

输入

第一行包含一个整数 N 。
接下来 N 行，第 i 行包含一个整数 Ai，表示第 i 位同学的得分。

输出

N 行，第 i 行包含一个整数，表示第 i 位同学的排名。

样例

输入

5
95
100
99
99
96

输出

5
1
2
2
4

说明

数据范围
对于 30% 的数据，N≤10。
对于 60% 的数据，N≤1000。
对于 100% 的数据，1≤N≤100000，0≤Ai≤1000000
【注意】
由于本题读入、输出的数据较多，C++选手请使用scanf和printf 替代 cin和cout 提升读写效率。

来源

常州市2015“信息与未来”夏令营选拔赛

代码1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
    int index;
    int score;
};

bool compare(Student a, Student b) {
    return a.score > b.score;
}

int main() {
    int N;
    scanf("%d", &N);

    vector<Student> students(N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &students[i].score);
        students[i].index = i;
    }

    sort(students.begin(), students.end(), compare);

    vector<int> ranks(N);
    for (int i = 0; i < N; i++) {
        if (i > 0 && students[i].score == students[i - 1].score) {
            ranks[students[i].index] = ranks[students[i - 1].index];
        } else {
            ranks[students[i].index] = i + 1;
        }
    }

    for (int i = 0; i < N; i++) {
        printf("%d\n", ranks[i]);
    }

    return 0;
}

在上述代码中，我们首先使用scanf读取输入的N，表示同学的数量。然后，我们使用一个vector存储每位同学的得分和索引，方便排序后得到排名。接下来，我们使用sort函数对同学的得分进行降序排序，并将排名存储在ranks数组中。注意，如果有多位同学得分相同，他们应该有相同的排名。最后，我们使用printf按照顺序输出每位同学的排名。

需要注意的是，在本题中，为了提高读写效率，建议使用scanf和printf替代cin和cout。另外，题目中要求的排名是从1开始的，因此在存储排名时需要加1。

代码2

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> scores(N);
    unordered_map<int, int> counts;
    for (int i = 0; i < N; i++) {
        cin >> scores[i];
        counts[scores[i]]++;
    }

    vector<int> ranks(N);
    int rank = 1;
    for (int i = 0; i < N; i++) {
        int count = counts[scores[i]];
        counts[scores[i]]--;
        ranks[i] = rank;
        rank += count;
    }

    for (int i = 0; i < N; i++) {
        cout << ranks[i] << endl;
    }

    return 0;
}

在这个解决方案中，我们首先使用cin读取输入的N，表示同学的数量。然后，我们使用一个vector存储每位同学的得分，并使用一个unordered_map记录每个得分出现的次数。接下来，我们使用一个rank变量初始化排名为1，然后遍历每位同学的得分，根据得分出现的次数来确定排名，并更新rank变量。最后，我们使用cout按顺序输出每位同学的排名。

这种方法不需要对得分进行排序，而是通过计数得到每位同学的排名，因此更加简单。