题目解析与代码分析

题目描述

$李明$是个好学生。他总是在每次考试后向老师询问他在班上的排名，这让老师非常累。所以老师把班上所有学生的分数都给了他，让他自己得到他的排名。不过，他的同学那么多，他不能轻易知道自己的等级。所以他向你寻求帮助，你能帮助他吗？

输入与输出

输入

1. 第一行包含一个整数 $N$ （$1 \leq N \leq 10000$），表示$李明$所在班级的学生人数。
2. 接下来 $N$ 行，每行包含一个学生的名字，名字不超过 $30$ 个字母。
3. 下一行包含一个整数 $M$ （$1 \leq M \leq 50$），表示考试次数。
4. 接下来 $M$ 段，每段表示一次考试：
   • 每次考试有 $N$ 行，每行包含一个正整数 $S$ 和一个名字 $P$，表示学生 $P$ 在本次考试中获得了 $S$ 分。

输出

• 输出 $M$ 行，每行包含一次考试后$李明$的排名。排名由总分决定。如果$李明$与其他人的分数相同，他将永远在排名榜上排在其他人前面。

解题思路

总体思路

1.存储数据：使用 map 存储每个学生的总分，键为学生名字，值为总分。 2.模拟考试：每次考试更新每个学生的总分。 3.计算排名：

• 将所有学生的总分排序。
• 查找$李明$的总分在排序后的数组中的位置，计算排名为 $N - pos$（因为排名从 $1$ 开始）。

具体步骤

1.初始化：

• 读取 $N$ 和学生名单。
• 初始化一个 map 存储每个学生的总分，初始值为 $0$。 2.处理考试：
• 对于每次考试：
  • 更新每个学生的总分。
  • 如果当前学生是 $Li Ming$，记录其总分。 3.计算排名：
• 将所有学生的总分存入数组并排序。
• 使用二分查找找到 $Li Ming$ 的总分在排序后的数组中的位置。
• 输出排名为 $N - pos$。

标程

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;

const int N = 10010;

int main() {
    //freopen("1.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF) {
        string ss;
        getchar();
        map<string, int> mp;
        map<string, int>::iterator it;
        for (int i = 0; i < n; ++i) {
            getline(cin, ss);
            mp[ss] = 0; // 初始化每个学生的总分为 0
        }

        int m;
        scanf("%d", &m);
        getchar();
        for (int i = 0; i < m; ++i) {
            int value = 0, score = 0;
            for (int j = 0; j < n; ++j) {
                scanf("%d", &score);
                getchar();
                getline(cin, ss);
                mp[ss] += score; // 更新每个学生的总分
                if (ss == "Li Ming") {
                    value = mp[ss]; // 记录 Li Ming 的总分
                }
            }

            int cnt = 0, num[N];
            for (it = mp.begin(); it != mp.end(); ++it) {
                num[cnt++] = it->second; // 将所有学生的总分存入数组
            }
            sort(num, num + cnt); // 排序总分数组

            // 二分查找 Li Ming 的总分位置
            int lp = 0, rp = cnt - 1, ans = 0;
            while (lp <= rp) {
                int mid = (lp + rp) / 2;
                if (num[mid] <= value) {
                    ans = mid;
                    lp = mid + 1;
                } else {
                    rp = mid - 1;
                }
            }
            printf("%d\n", n - ans); // 输出排名
        }
    }
    return 0;
}