区间问题

可以尝试左端点排序，右端点排序，双关键字排序

区间选点

原题链接

贪心思路：

  1. 将所有区间按照右端点排序
  2. 从前往后依次枚举每个区间
    1. 如果当前区间中已经包含点，直接跳过
    2. 否则选择当前区间右端点

证明：

假设最少的选择方案需要选出 ans 个点，按照上面的算法选出了 cnt 个点。显然 ans ≤ cnt。

按照上述算法能够选出 cnt 个互相不重叠的区间，这些区间中都被选中了右端点，要想让所有区间内都有点，最少选择的点 ans ≥ cnt。

所以 ans = cnt，按照上述算法选出的点的数量就是最小数量。

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
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
struct Range {
  int l;
  int r;
  bool operator<(const Range &R) { return r < R.r; }
};
struct Range range[N];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> range[i].l >> range[i].r;
  }
  sort(range, range + n);
  int ed = -2e9;
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (range[i].l > ed) {
      res++;
      ed = range[i].r;
    }
  }
  cout << res << endl;
  return 0;
}

最大不相交区间数量

原题链接

与上题做法一样。代码也一样。

区间分组

原题链接

算法：

  1. 将所有区间按照左端点排序
  2. 从前往后处理每个区间
    1. 判断能否将其放入某个现有的组中（这个组中任何区间与当前区间没有交集，L[i] > Max_r）
      1. 如果不存在这样的组，开一个新的组将其放进去
      2. 如果存在这样的组，将其放进去，并更新这个组的 Max_r

证明：

设 ans 为最小组数，cnt 为按照上述算法得到的组数。显然 ans ≤ cnt。

在新开第 cnt 个组的时刻，前 cnt - 1 个组中，每个组的 Max_r ≥ L[i]。加上当前的区间，一共可以找到 cnt 个区间，这些区间都有公共点 l[i]，所以这 cnt 个区间任意两个区间都不能分到一个组里，每个区间必须单独分到一个组，因此 ans ≥ cnt。

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

using namespace std;

const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range &W) { return l < W.l; }
} range[N];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> range[i].l >> range[i].r;
  }
  // 定义一个小根堆，维护当前创建的每个组中右端点的最小值
  priority_queue<int, vector<int>, greater<int>> heap;
  sort(range, range + n);
  for (int i = 0; i < n; i++) {
    // 判断当前区间能否放到一个现有的组里
    if (heap.empty() || heap.top() >= range[i].l)
      heap.push(range[i].r);
    else {
      auto t = heap.top();
      heap.pop();
      // 创建新组
      heap.push(range[i].r);
    }
  }
  cout << heap.size() << endl;
  return 0;
}

区间覆盖

原题链接

算法：

  1. 将所有区间按照左端点从小到大排序
  2. 从前往后依次枚举每个区间
    1. 在所有能覆盖 start 的区间中选择右端点最大的区间
    2. 将 start 更新成右端点的最大值

证明：

通过调整法可以直接证明。假设最优解的区间数为 ans，上述算法计算出的最小区间数为 cnt。从前往后依次枚举最优解选法的每个区间和按照算法计算的解中的每个区间，找到第一个不一样的区间，设最优解 ans 中这个区间的右端点为 aia_i，设算法解 cnt 中这个区间的右端点为 cic_i，根据算法过程可知 ci>aic_i > a_i，所以可以将 aia_i 调整为 cic_i。对后续每个区间，都可以做这样的调整，因此 ans = cnt。

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
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;

struct Range {
  int l, r;
  bool operator<(const Range &W) { return l < W.l; }
} range[N];

int main() {
  int n;
  int st, ed;
  cin >> st >> ed;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
  sort(range, range + n);
  int res = 0;
  bool success = false;
  for (int i = 0; i < n; i++) {
    int j = i, r = -2e9;
    // 寻找所有能覆盖 start 点的区间中，右端点最靠右的区间
    while (j < n && range[j].l <= st) {
      r = max(r, range[j].r);
      j++;
    }
    // 如果都不能覆盖住 start 点，无解
    if (r < st) {
      res = -1;
      break;
    }
    res++;
    // 如果已经能够覆盖 end 点，成功
    if (r >= ed) {
      success = true;
      break;
    }
    // 更新 start 点，从右端点最靠右的区间的右端点继续考虑
    st = r;
    i = j - 1;
  }
  if (!success) res = -1;
  cout << res << endl;
  return 0;
}

哈夫曼树

合并果子

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
#include <iostream>
#include <queue>
using namespace std;

int main() {
  int n;
  cin >> n;
  priority_queue<int, vector<int>, greater<int>> heap;
  while (n--) {
    int x;
    cin >> x;
    heap.push(x);
  }
  int res = 0;
  while (heap.size() > 1) {
    int a = heap.top();
    heap.pop();
    int b = heap.top();
    heap.pop();
    res += a + b;
    heap.push(a + b);
  }
  cout << res << endl;
  return 0;
}