202506-排序(luogu-B4361)

GESP C++四级2025年6月真题。本题主要考查排序的应用。属于四级题中的正常题目。难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B4361 [GESP202506 四级] 排序

题目要求

题目描述

体育课上有 $n$ 名同学排成一队，从前往后数第 $i$ 位同学的身高为 $h_i$，体重为 $w_i$。目前排成的队伍看起来参差不齐，老师希望同学们能按照身高从高到低的顺序排队，如果身高相同则按照体重从重到轻排序。在调整队伍时，每次只能交换相邻两位同学的位置。老师想知道，最少需要多少次交换操作，才能将队伍调整成目标顺序。

输入格式

第一行，一个正整数 $n$，表示队伍人数。

接下来 $n$ 行，每行两个正整数 $h_i$ 和 $w_i$，分别表示第 $i$ 位同学的身高和体重。

输出格式

输出一行，一个整数，表示最少需要的交换次数。

输入输出样例 #1

输入 #1

5
1 60
3 70
2 80
4 55
4 50

输出 #1

8

输入输出样例 #2

输入 #2

5
4 0
4 0
2 0
3 0
1 0

输出 #2

1

说明/提示

对于所有测试点，保证 $1 \leq n \leq 3000$，$0 \leq h_i, w_i \leq 10^9$。

题目分析

本题是一道排序题目，主要考察冒泡排序的应用和计数。难度适中，需要注意排序规则的实现。

1. 数据结构设计

• 使用二维数组s_ary[3005][2]存储学生信息，第一维表示学生编号，第二维分别存储身高和体重
• 数组大小设置为3005是为了满足题目要求的最大范围($n \leq 3000$)，并留有余量

2. 核心算法思路

• 首先读入学生人数n
• 读入每个学生的身高和体重信息存入二维数组
• 使用冒泡排序的思想计算交换次数：
  • 外层循环遍历每个位置i
  • 内层循环遍历i后面的所有位置j
  • 如果位置i的学生需要和位置j的学生交换（即身高更低或身高相同但体重更轻），则计数加1（逆序对数量）
• 最后输出需要交换的总次数

3. 算法复杂度分析

1. 时间复杂度

   • 读入数据：$O(n)$
   • 计算交换次数：$O(n^2)$
   • 总体时间复杂度：$O(n^2)$

2. 空间复杂度

   • 存储学生信息：$O(n)$
   • 其他变量：$O(1)$
   • 总体空间复杂度：$O(n)$

示例代码

#include <iostream>

// 定义二维数组存储学生身高和体重信息
// s_ary[i][0]存储身高，s_ary[i][1]存储体重
int s_ary[3005][2];

int main() {
    // 读入学生人数
    int n;
    std::cin >> n;

    // 读入每个学生的身高和体重
    for (int i = 0; i < n; i++) {
        std::cin >> s_ary[i][0] >> s_ary[i][1];
    }

    // 计算需要交换的次数
    int count = 0;
    // 冒泡排序的交换次数计算
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 如果前面的学生身高小于后面的学生
            // 或者身高相同但体重小于后面的学生
            // 则需要进行交换，计数+1
            if (s_ary[i][0] < s_ary[j][0] || 
                (s_ary[i][0] == s_ary[j][0] && s_ary[i][1] < s_ary[j][1])) {
                count++;
            }
        }
    }

    // 输出最少需要的交换次数
    std::cout << count;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号