简要题意
山初始高度为 $d$ , 有 $n$ 个登山者, 每个登山者有技巧 $s_i$ 和整洁度 $a_i$ 两个值, 在 $d \leqslant s_i$ 时此登山者可登上山, 登上山后山的高度变为 $a_i$ , 求最多能有多少个登山者登顶.
$n \leqslant 5 \times 10^5 , 0 \leqslant d,a_i,s_i \leqslant 10^9$ .
题解
显然先删去 $s_i < d$ 的人, 他们没有任何用处.
剩下的人按照 $max(a_i,s_i)$ 排序, 若 $max(a_i,s_i)$ 相等则按 $s_i$ 从小到大排序.
证明
设排序后处理到第 $i$ 个人, 目前山高为 $d$ .
$max(a_i,s_i)$ 为 $s_i$ 时, 显然 $s_i \geqslant d$ .
这种情况可以直接更新答案.
证明为什么这种情况直接更新答案是最优的:
分两种情况考虑.
$i$ 之后的所有 $max(a_j,s_j)$ 的取值都为 $s_j$ , 则 $a_i$ 不会对后面的人造成任何影响, 因为 $s_j \geqslant s_i \geqslant a_i$ .
$i$ 之后至少有一个人 $max$ 的取值为 $a_j$ , 设取到 $a_j$ 的这个人为 $k$ .
$i+1$ 到 $k-1$ 上的人同上.
若 $s_k \geqslant a_i$ 则 $a_i$ 不会对 $k$ 造成影响.
如果非要让$k$过去, 至少可以让 $i$ 先过去, 答案不会变大, 但因为 $a_k \geqslant a_i$ , 所以 $d$ 不会变小, 所以这种情况选 $i$ 是最优的.
有多个可能的 $k$ 同理.
$max(a_i,s_i)$ 为 $a_i$ 时, 显然 $a_i \geqslant d$ .
若此时 $s_i \geqslant d$ 则直接更新, 证明同上.
否则不更新答案, 如果非要让这个人登山, 至少要让之前的一个人不去, 总答案不变, $d$ 不会更小, 所以不选择这个人更优.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
int f = 1,c = getchar();x = 0;
while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
return read(x) && read(args...);
}
namespace run {
const int maxn = 5e5+10;
struct node {int s,a;}a[maxn];
int n,d,ans;
inline int main() {
read(n,d);
for (register int i = 1;i <= n;++i)read(a[i].s,a[i].a);
sort(a+1,a+1+n,[] (node u,node v) {return max(u.a,u.s) < max(v.a,v.s) || (max(u.s,u.a) == max(v.s,v.a) && u.s < v.s);});
for (register int i = 1;i <= n;++i)
if (a[i].s >= d) {
d = max(d,a[i].a);
ans++;
}
printf("%d\n",ans);
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
}
#define demonlover
int main() {
#ifdef demonlover
freopen("CF1602F.in","r",stdin);
freopen("CF1602F.out","w",stdout);
#endif
return run :: main();
}
|