1185: 猴子选大王（结构体专题）c语言讲解

这是一道经典的结构体题目，题目描述如下：

有n只猴子，它们称王称霸，它们之间的关系是顺序固定的。从1到n依次编号，第一只猴子为大王，第二只为大王的第一位臣子，第三只为大王的第二位臣子，以此类推。每只猴子有一个能力值，用一个整数来表示，能力值越大，排位越靠前。有一天，猴子们闹翻了，它们决定比试一下谁的能力值最大。比试时，每只猴子都可以选择站在原来的位置或者交换位置。一个猴子只能进行一次操作。当所有猴子的操作都完成后，谁的能力值最大，谁就当大王。现在请你编写程序，计算一下在所有猴子都采取最优策略的情况下，能力值最大的猴子可能达到多少。

首先我们需要定义一个猴子的结构体，包括编号和能力值两个成员：

struct Monkey {
    int num; // 编号
    int power; // 能力值
};

然后，我们需要对这些猴子按照能力值从大到小进行排序，这里可以使用qsort函数：

int cmp(const void *a, const void *b) {
    struct Monkey *p = (struct Monkey *)a;
    struct Monkey *q = (struct Monkey *)b;
    return q->power - p->power;
}

qsort(monkeys, n, sizeof(struct Monkey), cmp);

接下来，我们需要按照猴子原来的顺序（即编号）来进行交换位置，这里可以使用一个数组pos来记录每只猴子的位置，pos[i]表示编号为i的猴子的当前位置（从0开始）。然后，我们从大王开始，依次尝试将它交换到它应该在的位置上。如果它应该在的位置上已经有比它更强的猴子了，则继续向后寻找。如果找到了一个比它更弱的猴子，则交换它们的位置。这里需要注意的是，每只猴子只能进行一次操作，因此如果它已经完成了一次操作，则不再进行。

最后，我们可以遍历所有猴子的能力值，选出最大的那个作为答案。

完整代码如下：