前言
update 2021.11.1 我本以为紫名就不用打 Div2 了，没想到有 Div2 上限是2100，但是可以打 Div1 了，好耶ヾ(✿ﾟ▽ﾟ)ノ
难得的阳间比赛(指比赛时间)，上大分！
虽然今天下午状态还行，可惜最后一场 Div2 没能AK，不过竟然上榜了！人生首次！
而且还是通过 Hack 了一个人从 rank5 翻到了 rank4，与机房大佬三连了。(rank2,3,4)
首次使用 Hack，体验极佳，下次继续。
所以水题解。
题目
题目大意：
有 (n) 位登山者和一座初始困难度为 (d) 的山，每位登山者有两个值 (s_i,a_i) 表示TA的技能点和邋遢度。
登山者 (i) 可以登山的前提是其困难度不超过 (s_i)，当登山者 (i) 成功登山后，困难度会变为 (max(d,a_i))。
你需要找到一个合适的登山顺序以保证有最多的人成功登山，输出最大人数。
(1le nle 5 imes 10^5;0le d,s_i,a_ile 10^9.)
讲解
这个贪心真的NB，完全想不到，但是知道了之后直呼NB！
直接按 (max(s_i,a_i)) 的大小排序，如果相等按 (s_i) 大小排序，然后直接登山即可。
简单分类讨论一下：
- (s_i<a_j)，这里指的是 (i) 的最大值为 (s_i)，(j) 的最大值为 (a_j)，下同。此时如果把 (j) 放前面，(j) 如果成功上山，那么 (i) 一定上不了，不如先让 (i) 试试，不优。
- (a_i<s_j)，强的留在后面总是不劣的。
- (s_i<s_j)，同理不劣。
- (a_i<a_j)，此时 (j) 如果上山，(i) 一定上不了山，显然取邋遢度小的在前更优。
取等情况其实也差不多是这些思路，这道题就当缴智商税了。
时间复杂度 (O(nlog_2n))，瓶颈在排序。
还有码量较大的线段树优化DP做法，这里就不说了。
代码
超短代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 500005;
int n,d;
int s[MAXN],a[MAXN],p[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); d = Read();
for(int i = 1;i <= n;++ i) s[i] = Read(),a[i] = Read(),p[i] = i;
sort(p+1,p+n+1,[](int x,int y){
if(Max(s[x],a[x]) ^ Max(s[y],a[y])) return Max(s[x],a[x]) < Max(s[y],a[y]);
return s[x] < s[y];
});
int ans = 0;
for(int i = 1;i <= n;++ i)
if(s[p[i]] >= d) ++ans,d = Max(d,a[p[i]]);
Put(ans,'
');
return 0;
}
后记
有老哥按 (a_i+s_i) 和 (a_i imes s_i) 排序，都过了！/jk
update ? 也可以用类似上面的方法证明。