提供一个题解区没有提出的想法

没有详细证明，就不交题解了（而且这题题解也满了），只是提供另一种思路。

不妨把登山者分为

s_i < a_i

和

s_i \ge a_i

两类。

如果我们只单独考虑第一类，容易发现按照

a_i

升序贪心考虑（能登山就登）一定是最优的；如果我们只单独考虑第二类，按照

s_i

升序贪心考虑一定是最优的。这两个的证明是简单的。

那么显然考虑两种情况同时出现，首先可以证明的是同一类之间的登山者贪心的相对顺序是不变的，证明的话就考虑如果其与原顺序不同，我交换回来一定是不会劣的。

这样我们只需要考虑当前两类的最优决策

u

和

v

如何选择了：

如果 $a_u \le s_v$ ，那么我们选择 $u$ 不会对第二类决策产生任何影响，那不选白不选，我们当然会先选择 $u$ 。
否则你发现如果我们选了 $u$ 那就不能选 $v$ 了，且得到新的 $d'=a_u > s_v$ 。这不好，因为我们换成选择 $v$ 可以得到新的 $d''=\max\{d,a_v\}\le s_v < d'$ ，所以选择 $v$ 显然是更优的。

于是直接这样贪心即可。

仔细分析的话会发现这个思路与题解区按照

(\max\{s_i,a_i\},s_i)

进行双关键字再贪心的思路本质相同，但是我个人认为这个思路更加自然明了（

讨论操作