题解 | #小红的校招笔试#

题目链接

小红的校招笔试

题目描述

共有 $n$ 位同学参加校招笔试，给出了所有人的分数。

过线规则如下：

过线率为 50%，过线人数为 $n/2$ (向下取整)。
过线分数线为第 $n/2$ 名同学的分数。
所有分数大于或等于过线分数线的同学都会过线。
如果只有 1 位同学，该同学必然过线。

小红是第一个输入分数的同学，问她最终是否能过线。

解题思路

这个问题的核心是确定“过线分数线”，然后将小红的分数与之比较。

1. 确定过线分数线

要找到第 $k$ 名的分数，最直接有效的方法就是对所有分数进行排序。

我们将所有 $n$ 个分数从高到低进行降序排列。
根据规则，过线人数为 $n/2$ （整数除法，自动向下取整）。
那么，分数线就是排序后第 $n/2$ 个人的分数。在 0-indexed 的数组中，这个分数位于索引 (n/2) - 1 的位置。

2. 判断小红是否过线

我们首先需要记录下小红的原始分数（即输入的第一个分数）。
在计算出过线分数线 cutoff_score 后，我们只需判断小红的分数是否大于或等于 cutoff_score。
if (score_xiaohong >= cutoff_score)，则小红过线。

3. 处理特殊情况

当 $n=1$ 时，过线人数为 $1/2 = 0$ ，此时用 (n/2) - 1 计算索引会出错。根据题目明确说明，当只有一位同学时，必然过线。我们需要在代码中单独处理这个边界情况。

算法步骤总结

读取总人数 $n$ 和所有人的分数。单独存储小红的分数 score_xiaohong。
如果 $n=1$ ，直接输出 "Yes" 并结束程序。
将所有分数的数组进行降序排序。
计算过线人数的排名 rank = n / 2。
获取过线分数线 cutoff_score = sorted_scores[rank - 1]。
比较 score_xiaohong 和 cutoff_score，并输出 "Yes" 或 "No"。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> scores(n);
    int score_xiaohong;
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
        if (i == 0) {
            score_xiaohong = scores[i];
        }
    }

    if (n == 1) {
        cout << "Yes" << endl;
        return 0;
    }

    sort(scores.rbegin(), scores.rend());

    int pass_rank = n / 2;
    int cutoff_score = scores[pass_rank - 1];

    if (score_xiaohong >= cutoff_score) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        List<Integer> scores = new ArrayList<>();
        int scoreXiaohong = 0;
        
        for (int i = 0; i < n; i++) {
            int score = sc.nextInt();
            if (i == 0) {
                scoreXiaohong = score;
            }
            scores.add(score);
        }

        if (n == 1) {
            System.out.println("Yes");
            return;
        }

        scores.sort(Collections.reverseOrder());

        int passRank = n / 2;
        int cutoffScore = scores.get(passRank - 1);

        if (scoreXiaohong >= cutoffScore) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str:
        return
    n = int(n_str)
    
    scores = list(map(int, sys.stdin.readline().split()))
    score_xiaohong = scores[0]
    
    if n == 1:
        print("Yes")
        return
        
    scores.sort(reverse=True)
    
    pass_rank = n // 2
    cutoff_score = scores[pass_rank - 1]
    
    if score_xiaohong >= cutoff_score:
        print("Yes")
    else:
        print("No")

solve()

算法及复杂度

算法：排序
时间复杂度: $\mathcal{O}(n \log n)$ ，主要由对 $n$ 个分数进行排序的开销决定。
空间复杂度: $\mathcal{O}(n)$ ，用于存储 $n$ 位同学的分数。