[CF1601]Difficult Mountain

发表于

link

标签

贪心 + 双指针 + 分类讨论

思路

首先考虑把人分成两类分别是 ai≤sia_i \leq s_i 和 si<ais_i < a_i . 考虑这两种情况分别怎么解决

ai <= si

直接按 sis_i 排序。每个人都能爬上山。证明如下:

如果一个人的 sis_i 大于前面人的 sis_i 那么一定大于前面人的 aia_i . 所以每个人都能爬上山

ai > si

发现可以把每个人看成一条线段，然后就转化为了选择一些互不相交且互不包含的线段，另选择的线段数最多。这是一个经典的问题。把所有线段按 aia_i 排序，从前往后能选就选。

综合考虑

称 ai≤sia_i \leq s_i 的人为原人， ai>sia_i > s_i 的人为贡献人
考虑把贡献人加入到原人中。方法就是如果加入的贡献人不会和原人冲突，那就加入。否则一定不加入。证明：

考虑加入一个贡献人，因为其它贡献人和它并不相交，所以那些和它冲突的原人一定只和它冲突。即如果冲突后删除原人，贡献最多为 11 。但是原人的数量至少减少 11 , 这样做一定不会更优。

所以得出做法：

  1. 把原人和贡献人按照上述方法排序，
  2. 用双指针分别指向原人和贡献人。
  3. 不断加入贡献人直到新加入的贡献人和后面的一个原人冲突，如果冲突就不加入这个贡献人并停止加入。
  4. 加入一个原人并重复 3,43, 4

code

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;
int n, d;
pair<int, int> q1[N], q2[N];
int tot1, tot2;
int s[N], a[N];

int main() {
  scanf("%d%d",  &n, &d);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &s[i], &a[i]);
    if (s[i] < a[i]) {
      q1[++tot1] = make_pair(a[i], s[i]);
    }
    else {
      q2[++tot2] = make_pair(s[i], a[i]);
    }
  }
  int j = 1;
  int ans = 0;
  sort(q1 + 1, q1 + tot1 + 1);
  sort(q2 + 1, q2 + tot2 + 1);
  for (int i = 1; i <= tot2; ++i) {
    while (j <= tot1 && q1[j].first <= q2[i].first) {
      if (d <= q1[j].second) {
        ++ans;
        d = max(d, q1[j].first);
      }
      ++j;
    }
    if (q2[i].first >= d) {
      d = max(d, q2[i].second);
      ++ans;
    }
  }
  while (j <= tot1) {
    if (d <= q1[j].second) {
      ++ans;
      d = max(d, q1[j].first);
    }
    ++j;
  }
  cout << ans << endl;
  return 0;
}