统计班级中的说谎者（字节青训）

题目

班里有 N 个学生，第 i 个学生的分数是 A_i。当且仅当分数 <= A_i 的学生数量多于分数比他高的数量时，第 i 个学生会说谎。求出有多少学生会说谎。

输入格式

• 输入 N 学生的成绩，包含 A_1, A_2, ..., A_N

输出格式

对于每组数据，输出有多少学生会说谎。

数据范围

• 1≤N≤1001≤N≤100

• 0≤Ai≤1000≤Ai​≤100

输入

100 100 100

输出

3

输入

2 1 3

输出

2

demo

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

int solution(std::vector<int> A) {
    int N = A.size();
    std::unordered_map<int, int> score_count;

    // 统计每个分数的出现次数
    for (int score : A) {
        score_count[score]++;
    }

    // 计算说谎的学生数量
    int liars = 0;
    int cumulative_count = 0; // 记录分数小于当前分数的学生数量

    // 获取所有分数并排序
    std::vector<int> unique_scores;
    for (const auto& pair : score_count) {
        unique_scores.push_back(pair.first);
    }
    std::sort(unique_scores.begin(), unique_scores.end());

    // 遍历每个分数
    for (int score : unique_scores) {
        // 当前分数的学生数量
        int current_count = score_count[score];

        // 分数小于等于当前分数的学生数量
        int less_equal_count = cumulative_count + current_count;

        // 分数高于当前分数的学生数量
        int greater_count = N - less_equal_count;

        // 判断是否说谎
        if (less_equal_count > greater_count) {
            liars += current_count; // 所有分数为 score 的学生都说谎
        }

        // 更新累计计数
        cumulative_count += current_count;
    }

    return liars;
}

int main() {
    // Add your test cases here
    std::cout << (solution({100, 100, 100}) == 3) << std::endl;
    std::cout << (solution({2, 1, 3}) == 2) << std::endl;
    std::cout << (solution({30, 1, 30, 30}) == 3) << std::endl;
    std::cout << (solution({19, 27, 73, 55, 88}) == 3) << std::endl;
    std::cout << (solution({19, 27, 73, 55, 88, 88, 2, 17, 22}) == 5) << std::endl;
    return 0;
}

• 使用 cumulative_count 来记录分数小于当前分数的学生数量。
• 在遍历 unique_scores 时，计算每个分数的 less_equal_count 和 greater_count