专栏文章

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

II_am_kunzi
P14593题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1bam9
此快照首次捕获于
2025/12/01 18:57
3 个月前
此快照最后确认于
2025/12/01 18:57
3 个月前
查看原文

P14593 题解

题目思路

首先题目中已经明确说了，这题的核心就是给 nn 场比赛钦定一个顺序，那么我们先分析一下每场比赛的难度 aa 和隐藏分 bb 的作用。
难度 a a：只有当前能力值 xx 不大于难度时才会打这场比赛。即难度是打这场比赛的能力值上限，能力值越小，能打的比赛越多。
隐藏分 b b：如果打了某场比赛，那么能力值变为 max⁡(b,x) \max(b , x)。即隐藏分用于更新能力值。
如果两场比赛的四个参数 a1,b1,a2,b2a_1 , b_1 , a_2 , b_2 中，a2,b2a_2 , b_2 中任意一个都不小于 a1,b1a_1 , b_1 中任意一个，那么先打第一场比赛一定更优，因为打完之后能力值不可能比 a2a_2 大。所以在此情况下，按照 max⁡(a,b)\max(a , b) 从小到大排序是正确的。
如果不满足上一段的条件，不妨分讨第一场比赛中哪个参数最大，这个参数一定大于第二场比赛中最小的参数，进一步只需要分讨这两组参数内大小关系。然后又很自然发现两组参数内大小关系确定了之后，只要再确定 max⁡(a1,b1)\max(a_1 , b_1) 和 max⁡(a2,b2)\max(a_2 , b_2) 的大小关系即可确定四个参数的关系，注意上一段已经讨论过的情况无需讨论，所以只用再知道两参数内最大值是正确的。
那么……又绕回来了。不妨直接钦定 max⁡(a1,b1)<max⁡(a2,b2) \max(a_1 , b_1) < \max(a_2 , b_2)，然后再分讨两组参数内大小关系，共四种情况。
  1. a1<b1,a2<b2a_1 < b_1 , a_2 < b_2，结合最大值的关系即 a1<a2<b1<b2 a_1 < a_2 < b_1 < b_2。此时打了第一场就不能打第二场，打了第二场就不能打第一场。打第一场给能力值的增加更小，根据最开头的分析，这样更优。所以先打第一场。
  2. b1<a1,a2<b2b_1 < a_1 , a_2 < b_2，结合最大值的关系即 b1<a2<a1<b2 b_1 < a_2 < a_1 < b_2。此时打了第一场还能打第二场，打了第二场不能打第一场。所以先打第一场。
  3. a1<b1,b2<a2a_1 < b_1 , b_2 < a_2，结合最大值的关系即 a1<b2<b1<a2 a_1 < b_2 < b_1 < a_2。分析同第二条。所以先打第一场。
  4. b1<a1,b2<a2b_1 < a_1 , b_2 < a_2，结合最大值的关系即 b1<b2<a1<a2 b_1 < b_2 < a_1 < a_2。此时无论先打哪场都可以两场都打，而且最终能力值与顺序无关，那么顺应通用规律写代码更方便。所以先打第一场。
这样不知不觉就证明了这个贪心的正确性。
但此时漏讨论了 max⁡(a1,b1)=max⁡(a2,b2)\max(a_1 , b_1) = \max(a_2 , b_2) 的情况。此时如果四个参数都相等，就没必要讨论了，两场比赛都可以打。所以如果先打隐藏分小的比赛，有可能就打不了难度小的比赛；而先打难度小的比赛，此时这场比赛的隐藏分与另一场比赛的难度相同，两场都可以打，一定不劣。
综上，如果 max⁡(a1,b1)=max⁡(a2,b2) \max(a_1 , b_1) = \max(a_2 , b_2)，就按难度 aa 从小到大排序，否则按 max⁡(a,b)\max(a , b) 从小到大排序。
这次真的做完了，我们的思路非常流畅，没有任何跳步和猜结论的过程。

题目代码

上文讲解应该很清楚了，不需要注释大概也能看懂代码。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...