题解：P14593 [LNCPC 2025] 猫猫虫打 CF

· · 题解

P14593 题解

题目思路

首先题目中已经明确说了，这题的核心就是给 n 场比赛钦定一个顺序，那么我们先分析一下每场比赛的难度 a 和隐藏分 b 的作用。

难度 a：只有当前能力值 x 不大于难度时才会打这场比赛。即难度是打这场比赛的能力值上限，能力值越小，能打的比赛越多。

隐藏分 b：如果打了某场比赛，那么能力值变为 \max(b , x)。即隐藏分用于更新能力值。

如果两场比赛的四个参数 a_1 , b_1 , a_2 , b_2 中，a_2 , b_2 中任意一个都不小于 a_1 , b_1 中任意一个，那么先打第一场比赛一定更优，因为打完之后能力值不可能比 a_2 大。所以在此情况下，按照 \max(a , b) 从小到大排序是正确的。

如果不满足上一段的条件，不妨分讨第一场比赛中哪个参数最大，这个参数一定大于第二场比赛中最小的参数，进一步只需要分讨这两组参数内大小关系。然后又很自然发现两组参数内大小关系确定了之后，只要再确定 \max(a_1 , b_1) 和 \max(a_2 , b_2) 的大小关系即可确定四个参数的关系，注意上一段已经讨论过的情况无需讨论，所以只用再知道两参数内最大值是正确的。

那么……又绕回来了。不妨直接钦定 \max(a_1 , b_1) < \max(a_2 , b_2)，然后再分讨两组参数内大小关系，共四种情况。

这样不知不觉就证明了这个贪心的正确性。

但此时漏讨论了 \max(a_1 , b_1) = \max(a_2 , b_2) 的情况。此时如果四个参数都相等，就没必要讨论了，两场比赛都可以打。所以如果先打隐藏分小的比赛，有可能就打不了难度小的比赛；而先打难度小的比赛，此时这场比赛的隐藏分与另一场比赛的难度相同，两场都可以打，一定不劣。

综上，如果 \max(a_1 , b_1) = \max(a_2 , b_2)，就按难度 a 从小到大排序，否则按 \max(a , b) 从小到大排序。

这次真的做完了，我们的思路非常流畅，没有任何跳步和猜结论的过程。

题目代码

上文讲解应该很清楚了，不需要注释大概也能看懂代码。

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(pair < long long , long long > a , pair < long long , long long > b)
{
    if(max(a.first , a.second) == max(b.first , b.second))
    {
        return a.first < b.first;
    }
    return max(a.first , a.second) < max(b.first , b.second);
}
pair < long long , long long > a[1000005];
int n;
signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    long long x = 0;
    sort(a + 1 , a + n + 1 , cmp);
    int ans = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        if(x <= a[i].first)
        {
            ans++;
            x = max(x , a[i].second);
        }
    }
    cout << ans << endl;
    return 0;
}