P10728 Solution

OIerWu_829 · 2024-07-09 17:32:01 · 题解

题目传送门

作为这道题除出题人外的首个 AC 而且代码长度比出题人短，来写篇题解。

直接暴力对于 n\le 10^5 肯定不行，考虑优化。

首先将所有剑按照攻击力从大到小排序，如果攻击力相同则按防御力从大到小排序，这样一来任何一把剑后面的剑的攻击力都会比它小。然后对于每一把剑，如果这把剑的防御力大于之前的最大防御力，那么这把剑就是有用的，因为它没有在任何方面被后面的剑所超越，然后更新最大防御力，最后输出答案。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

struct Node {
    int a, b;
} p[N];

bool cmp(Node x, Node y) {
    if (x.a != y.a)
        return x.a > y.a;
    return x.b > y.b;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].a >> p[i].b;
    sort(p + 1, p + 1 + n, cmp);
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i++)
        if (p[i].b > mx)
            ans++, mx = p[i].b;
    cout << ans;
    return 0;
}