【例75.1】 坐标统计

解题思路

对每个点i枚举所有点j，只有xj<xi且yj<yi才加战斗力。输出每个计数，再比较所有计数，遇到相等也更新，使最后保留最大编号。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

坐标需同时严格小于，相等不算控制。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> x(n), y(n), power(n);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (x[j] < x[i] && y[j] < y[i])
                power[i]++;
    int best = 0;
    for (int i = 0; i < n; i++) {
        cout << power[i] << "\n";
        if (power[i] >= power[best])
            best = i;
    }
    cout << best + 1 << "\n";
    return 0;
}