C语言qsort实现PKU ACM 1828题猴子骄傲排序详解

在ACM PKU（北京大学ACM竞赛平台）的第1828题"Monkeys' Pride"中，题目要求我们使用C语言实现快速排序算法（qsort）来对一组猴子结构体数组进行排序。该结构体`struct st`包含两个整数成员x和y。题目主要关注按照两种情况对猴子进行排序：首先根据x值升序，如果x值相同，则根据y值降序排列。 核心知识点如下： 1. **数据结构定义**： `struct st` 定义了一个猴子的结构体，包含两个成员变量：`int x` 和 `int y`，分别代表每个猴子的编号和骄傲值。 2. **比较函数（cmp）**： - 这个函数是快速排序的关键部分，采用C语言的指针作为参数。函数接收两个猴子结构体指针`p`和`q`。 - 在`cmp`函数中，首先判断`x`值的大小，如果不同则返回`q`的`x`值大于`p`的`x`值时为正（即升序），反之为负。如果`x`值相等，则比较`y`值，返回`q`的`y`值大于`p`的`y`值时为正（即降序），反之为负。 3. **主函数（main）**： - 输入部分：通过循环读取猴子的数量`t`，以及每个猴子的编号`x`和骄傲值`y`，并将它们存储到`monkey`数组中。 - 排序部分：调用`qsort`函数对`monkey`数组进行排序，使用之前定义的`cmp`函数作为比较器，指定数组元素大小和类型。 - 分析结果：初始化变量`sum`为1，表示猴子群体中骄傲值最大的猴子数量。遍历排序后的数组，统计具有最大骄傲值的猴子数量（`max`），同时累加`sum`。当遇到骄傲值更大的猴子时，`sum`加一。 - 输出结果：最后输出满足条件的猴子数量`sum`。 总结来说，这个C语言程序解决的是一个在ACM PKU竞赛中常见的问题，涉及到了数据结构、比较函数设计以及快速排序算法的运用，展示了如何根据题目要求灵活处理数组排序，并统计特定条件下的元素数量。对于学习C语言编程或准备参加ACM竞赛的学生来说，这是一个很好的实战练习案例。