1 条题解

  • 1
    @ 2025-4-9 22:13:05

    题意分析:

    给定NN个包含MM个选手的周排名,统计每个选手的总出现次数(每个出现计11分)。要求找出所有得分严格小于最高分最大的次高分数对应的选手。需要处理多个选手并列第二的情况,并按升序输出他们的标识符。

    解题思路:

    1. 统计得分
      定义数组count[ ]count[\ ],其中count[id]count[id]表示选手idid的总得分。初始化时满足:

      count[id]=0,id[1,10000]count[id] = 0, \quad \forall id \in [1, 10000]

      对每个输入的周排名,执行:

      $$\forall id \in \text{当前周排名}, \quad count[id] \leftarrow count[id] + 1 $$
    2. 确定最高分
      遍历所有id[1,10000]id \in [1, 10000],计算:

      $$max\_score = \max_{1 \leq id \leq 10000} count[id] $$
    3. 确定次高分
      再次遍历,计算严格小于max_scoremax\_score的最大值:

      $$sec\_score = \max_{\substack{1 \leq id \leq 10000 \\ count[id] < max\_score}} count[id] $$
    4. 收集结果并排序
      定义集合SS为所有次高分的选手:

      S={idcount[id]=sec_score}S = \{ id \mid count[id] = sec\_score \}

      SS按升序排列,输出时满足:

      $$\forall id \in S, \quad id_1 < id_2 < \dots < id_k $$

      其中kk为集合SS的元素个数。

    代码

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int main() {
        int N, M;
        while (cin >> N >> M && (N != 0 || M != 0)) {
            int count[10001] = {0}; // 初始化计数器数组
            
            // 读取所有排名数据并统计
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < M; ++j) {
                    int id;
                    cin >> id;
                    count[id]++;
                }
            }
            
            // 找出最高分
            int max_score = 0;
            for (int i = 1; i <= 10000; ++i) {
                if (count[i] > max_score) {
                    max_score = count[i];
                }
            }
            
            // 找出第二高分
            int sec_score = 0;
            for (int i = 1; i <= 10000; ++i) {
                if (count[i] < max_score && count[i] > sec_score) {
                    sec_score = count[i];
                }
            }
            
            // 收集所有第二高分的玩家并按升序排列
            vector<int> second_place;
            for (int i = 1; i <= 10000; ++i) {
                if (count[i] == sec_score) {
                    second_place.push_back(i);
                }
            }
            sort(second_place.begin(), second_place.end());
            
            // 输出结果
            for (int id : second_place) {
                cout << id << " ";
            }
            cout << endl;
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1093
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    10
    已通过
    1
    上传者