题解：猴王问题

题目分析

题目要求我们在给定的一组猴子坐标中，找出符合“猴王”条件的猴子的数量。猴王的定义是：一个猴子的坐标为 ((x_i, y_i))，如果他的 (x) 坐标大于他左边所有猴子的 (x) 坐标且 (y) 坐标大于他左边所有猴子的 (y) 坐标，那么该猴子是猴王。

显然，猴王可能不止一个。我们需要设计一个有效的算法来解决这个问题。

解题思路

这个问题可以通过“贪心算法”来优化处理。

1. 排序：

   • 首先按照猴子坐标的 (x) 从小到大进行排序。如果有多个猴子的 (x) 相同，则按 (y) 从小到大排序。这是因为如果 (x_1 < x_2)，那么在 (x_1) 之前的猴子一定不可能成为以 (x_2) 为坐标的猴王，所以我们需要从小到大的顺序处理。

2. 贪心扫描：

   • 排序完成后，我们从右向左（从坐标最大的猴子开始）扫描猴子，记录当前扫描过的最大 (y) 值。如果当前扫描到的猴子的 (y) 值大于我们记录的最大 (y)，则该猴子是猴王，并更新当前最大 (y)。
   • 为了简化比较，我们还需要注意，若猴子的 (x) 相同，则后续的猴子无法成为猴王，因此可以跳过这类猴子的比较。

3. 关键思想：

   • 每次扫描时，猴子的 (y) 值必须比前面所有扫描过的猴子中的最大 (y) 值还大，才能成为猴王。扫描过程中，我们始终保持一个记录当前最大 (y) 值的变量。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int Max = 50005;

// 定义结构体 node 来保存每个猴子的坐标
struct node
{
    int x, y;  // x 和 y 分别表示猴子的坐标
} p[Max];

// 比较函数：先按 x 从小到大排序，如果 x 相同，则按 y 从小到大排序
int cmp(const node &a, const node &b)
{
    if (a.x != b.x)
        return a.x < b.x;  // 按 x 排序
    else
        return a.y < b.y;  // 如果 x 相同，则按 y 排序
}

int main()
{
    int n, i, total, tmp;
    while (cin >> n && n)  // 输入猴子数量 n，如果 n 为 0 则结束输入
    {
        total = 1;  // 初始时，假设最后一个猴子是猴王
        for (i = 0; i < n; i++)  // 输入所有猴子的坐标
        {
            cin >> p[i].x >> p[i].y;
        }
        // 按照坐标排序
        sort(p, p + n, cmp);

        tmp = p[n - 1].y;  // 初始化最大 y 值为最后一个猴子的 y 值
        for (i = n - 2; i >= 0; i--)  // 从后往前扫描
        {
            if (p[i].y > tmp)  // 如果当前猴子的 y 值大于已扫描过的最大 y 值
            {
                total++;  // 该猴子是猴王
                tmp = p[i].y;  // 更新最大 y 值
            }
        }
        cout << total << endl;  // 输出猴王的个数
    }
    return 0;
}

代码解析

1. 输入部分：

   • 每次循环输入一组猴子的数量 (n)，然后读取 (n) 个猴子的坐标。

2. 排序：

   • 使用 sort 函数按照猴子坐标的 (x) 从小到大排序，如果有多个猴子坐标的 (x) 相同，则按 (y) 从小到大排序。

3. 贪心扫描：

   • 从最后一个猴子开始扫描，记录扫描过的最大 (y) 值。如果当前猴子的 (y) 值大于最大值，则该猴子是猴王，更新最大 (y) 值并增加猴王的数量。
   • 如果当前猴子的 (y) 值小于等于最大 (y) 值，则跳过该猴子，不更新猴王数量。

4. 输出结果：

   • 每次循环完毕后，输出猴王的个数。

时间复杂度分析

1. 排序时间复杂度：

   • 排序操作的时间复杂度是 (O(n \log n))，其中 (n) 是猴子的数量。

2. 扫描时间复杂度：

   • 扫描过程是一次线性扫描，时间复杂度是 (O(n))。

因此，总时间复杂度为 (O(n \log n))。

总结

本题通过对猴子坐标的排序和贪心策略有效地找到了猴王的个数。通过从后向前扫描，保证了每次扫描时所遇到的猴子都符合成为猴王的条件。排序和贪心策略的结合，使得问题能够在 (O(n \log n)) 的时间复杂度下得到解决，适应了较大的输入规模。