【天梯赛L1-7】天梯赛的善良 - 最小/最大能力值统计

loopdeloop

已于 2025-04-06 21:43:56 修改

阅读量216

点赞数 8

文章标签：算法 c++ 数据结构

于 2025-04-06 21:39:34 首次发布

本文链接：https://blog.csdn.net/loopdeloop/article/details/147030771

版权

一、题目描述

天梯赛命题组需要统计所有参赛学生的最小能力值和最大能力值，并统计具有这两个能力值的学生人数。
输入格式：

第一行：学生总数 N（≤ 2×10⁴）
第二行：N 个不超过 10⁶ 的正整数（能力值）

输出格式：

第一行：最小能力值 + 该能力值人数
第二行：最大能力值 + 该能力值人数

示例输入：

复制

10
86 75 233 888 666 75 886 888 75 666

示例输出：

复制

75 3
888 2

二、题目分析

核心需求：
- 找到数组中的最小值和最大值。
- 统计这两个值的出现次数。
关键点：
- 数据范围较大（N ≤ 2×10⁴），需用O(n)或O(nlogn)算法。
- 最小值/最大值可能有重复值，需正确计数。
- 暴力法（命题组看了会沉默）：
  - 直接遍历数组，记录最小值和最大值，再数一遍有几个。
  - 时间复杂度：O(n)（但写起来有点啰嗦）。
- 排序法（我选择偷懒）：
  - 先排序，最小值在开头，最大值在结尾。
  - 然后数数开头有多少个一样的，结尾有多少个一样的。
  - 时间复杂度：O(nlogn)（但代码短，适合我这种懒人）。
- 我选排序法！（因为STL的 sort 太好用了）

三、代码实现

#include<bits/stdc++.h>
using namespace std;
int main() {
    int a;
    cin >> a;
    int C[20005];
    for (int i = 1; i <= a; i++) {
        cin >> C[i];
    }
    sort(C + 1, C + 1 + a);  // 升序排序
    int numa = 1, numb = 1;   // 初始化最小/最大值的计数
    // 统计最小值出现次数
    for (int i = 1; i <= a; i++) {
        if (C[i] == C[i + 1]) numa++;
        else break;
    }
    // 统计最大值出现次数
    for (int i = a; i >= 0; i--) {
        if (C[i] == C[i - 1]) numb++;
        else break;
    }
    // 输出结果
    cout << C[1] << " " << numa << endl;
    cout << C[a] << " " << numb << endl;
    return 0;
}