CF1601D Difficult Mountain
2026-06-26
题目大意
有 n 个人要登山,初始攀登难度为 d。
每个人有两个属性:技巧 s 和整洁度 a。
技巧为 s 的人能登上当前难度 p 的山当且仅当 p≤s。
当一位整洁度为 a 的人成功登山后,山的难度会变为 max(p,a)。
你可以任意安排这些人的登山顺序,每个人若轮到且能登山则一定会登,求最多能让多少人成功登山。
数据范围:1≤n≤5×105,0≤d≤109,0≤si,ai≤109。
题解
首先我们排除所有 si<d 的人,显然他们没有用。
考虑贪心策略:将所有人以 max(ai,si) 排序,如果相同则以 si 升序排序。
证明:
若 max(ai,si)=si,即 ai≤si 时:
考虑在 i 以前的人,要么 max(sj,aj)<si,显然 d<si;要么 max(sj,aj)=si,则 d≤si。
所以,有 si≥d,此时可以直接更新答案。直接更新为什么更优?显然我们要考虑 i 以后的人,有两种情况:
- i 以后的全部取 sj,此时由于 sj≥si≥ai,不会产生影响。
- i 以后取一部分 sj,然后遇到一个取 ak 的人,记为 k。
如果 sk≥ai,显然 k 也可以去,不影响。
如果 sk<ai,要让 k 去必须至少让 i 不去,答案不会更大,又因为 ak≥ai,d 不会变小,一定不会更优。
若 max(ai,si)=ai,即 ai≥si 时:
与前面一样,有 d≤ai。
此时若 si≥d,可以直接去。
若 si<d,显然不能去,如果一定要去的话至少要让前面的一个人不去,d 不会更小,答案也不会更大,一定不会更优。
