小红的校招笔试

[题目链接](https://www.nowcoder.com/practice/15eb5f67d766438fb85aa11984edd88f)

思路

小红参加校招笔试，已知所有人的成绩，通过率为 50%（向下取整），需要判断小红是否通过。

关键规则

通过人数： $k = \lfloor n / 2 \rfloor$ ，即前 $k$ 名通过。
并列通过：如果有多人与第 $k$ 名分数相同，这些人全部通过。
特判：只有 1 人时直接通过（因为 $\lfloor 1/2 \rfloor = 0$ ，需要特殊处理）。

做法

将所有成绩降序排序，找到第 $k$ 名的分数作为通过线（threshold = a[k-1]，0 索引）。小红的分数 $\geq$ 通过线即通过。

并列规则不需要额外处理——只要小红分数 $\geq$ 通过线，无论是排在第 $k$ 名还是并列第 $k$ 名，都满足条件。

样例演示

样例 1： $n=4$ ，成绩 $[2,1,2,3]$ ，小红分数为 $2$ 。

$k = \lfloor 4/2 \rfloor = 2$
降序排序： $[3,2,2,1]$ ，通过线 $= a[1] = 2$
小红分数 $2 \geq 2$ ，输出 Yes

样例 2： $n=5$ ，成绩 $[4,5,2,1,6]$ ，小红分数为 $4$ 。

$k = \lfloor 5/2 \rfloor = 2$
降序排序： $[6,5,4,2,1]$ ，通过线 $= a[1] = 5$
小红分数 $4 < 5$ ，输出 No

复杂度分析

时间复杂度： $O(n \log n)$ ，排序的开销。
空间复杂度： $O(n)$ ，存储所有成绩。

代码

C++
Java
Python3
JavaScript

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int xiaohong = a[0];
    if (n == 1) {
        cout << "Yes" << endl;
        return 0;
    }
    sort(a.begin(), a.end(), greater<int>());
    int k = n / 2;
    int threshold = a[k - 1];
    if (xiaohong >= threshold) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int xiaohong = a[0];
        if (n == 1) {
            System.out.println("Yes");
            return;
        }
        Arrays.sort(a);
        int k = n / 2;
        int threshold = a[n - k];
        if (xiaohong >= threshold) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

n = int(input())
a = list(map(int, input().split()))
xiaohong = a[0]
if n == 1:
    print("Yes")
else:
    a.sort(reverse=True)
    k = n // 2
    threshold = a[k - 1]
    if xiaohong >= threshold:
        print("Yes")
    else:
        print("No")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', function(line) {
    lines.push(line.trim());
    if (lines.length === 2) {
        const n = parseInt(lines[0]);
        const a = lines[1].split(' ').map(Number);
        const xiaohong = a[0];
        if (n === 1) {
            console.log("Yes");
        } else {
            a.sort((x, y) => y - x);
            const k = Math.floor(n / 2);
            const threshold = a[k - 1];
            if (xiaohong >= threshold) {
                console.log("Yes");
            } else {
                console.log("No");
            }
        }
        rl.close();
    }
});