A5. 分数线划定 - 题解

---

题目分析

本题需要根据规则确定面试分数线，并输出进入面试的选手信息。主要步骤包括：

1. 确定面试分数线位置：根据公式 position = floor(m * 1.5) 找到第几名选手的分数作为分数线
2. 筛选进入面试的选手：所有成绩不低于分数线的选手都进入面试
3. 排序规则：
   • 先按笔试成绩从高到低排序
   • 成绩相同时，按报名号从小到大排序

解题思路

核心算法步骤

1. 数据存储：使用结构体存储每个选手的信息（报名号、成绩）
2. 排序：按照题目要求的排序规则进行排序
3. 确定分数线：
   • 计算分数线位置 line_index = floor(m * 1.5) - 1（数组下标从0开始）
   • 分数线分数为 scores[line_index].score
4. 统计实际人数：统计所有成绩不低于分数线的选手数量
5. 输出结果：按要求格式输出

时间复杂度

• 排序：O(n log n)，n ≤ 5000，完全可行
• 空间复杂度：O(n)

---

C++代码实现（all AC，可放心食用）

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

struct Player {
    int id;      
    int score;   
};

bool cmp(const Player &a, const Player &b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return a.id < b.id;
}

int main() {
    int n, m;
    scanf("%d%d",&n,&m);
    
    Player players[5005];
    
    
    for (int i = 0; i < n; i++)
        scanf("%d%d",&players[i].id,&players[i].score);
    
    // 排
    sort(players, players + n, cmp);
    
    // 计算线位
    int line_index = floor(m * 1.5) - 1;
    int line_score = players[line_index].score;
    
    
    int actual_count = 0;// 实际进入人数
    for (int i = 0; i < n; i++) {
        if (players[i].score >= line_score) {
            actual_count++;
        } else {
            break;  //已排，后面更小
        }
    }
    
    
    printf("%d %d\n",line_score,actual_count);
    for (int i = 0; i < actual_count; i++) 
        printf("%d %d\n",players[i].id,players[i].score);// 输出结果
    
    return 0;//不忘好习惯，歇菜
}

代码说明

关键点

1. 排序规则实现：

   bool cmp(const Player &a, const Player &b) {
       if (a.score != b.score) {
           return a.score > b.score;  // 成绩高的在前
       }
       return a.id < b.id;  // 成绩相同时，报名号小的在前
   }
   

2. 分数线计算：

   • m * 1.5 得到理论位置（可能是小数）
   • floor() 向下取整得到整数位置
   • 由于数组下标从0开始，需要减1：line_index = floor(m * 1.5) - 1

3. 实际人数统计：

   • 由于数组已按成绩降序排列，只需找到第一个成绩低于分数线的位置
   • 使用 break 提前结束循环提高效率

样例解析

输入：

6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

处理过程：

1. 计算分数线位置：floor(3 × 1.5) = floor(4.5) = 4，即第4名选手（下标3）
2. 排序后，下标3的选手成绩为88，所以分数线为88
3. 统计成绩≥88的选手：有5人
4. 输出结果

注意事项

1. 向下取整：必须使用 floor() 或整数除法实现向下取整
2. 数组下标：注意题目中的"第k名"与C++数组下标（从0开始）的转换
3. 边界情况：当分数线上有多人同分时，需要全部计入
4. 数据范围：n ≤ 5000，完全可以使用普通排序算法

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，存储选手信息

---

总结

本题是一道简单的排序应用题，关键在于理解题目描述的排序规则和分数线划定方法。按照题目要求实现排序和筛选即可得到正确答案。

蒜鸟蒜鸟，睡了