短视的行为

区间选点

给N个闭区间, 要在数轴上选尽量少的点, 使每个区间至少包含一个选出的点 (answer ≤ count)

区间贪心问题, 要么按左端点排序, 要么按右端点, 要么双关键字

  1. 每个区间按右端点从小到大排序
  2. 从前往后依次枚举每个区间
  • 如果已经包含点, pass
  • 否则选右端点 (answer ≥ count)
  • => answer = count
 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

#include <iostream>
#include <algorithm>

using namespace std;

const int N=100010;

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

int main(){
    scanf("%d", &n);
    for (int i=0; i < n; i++){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range+n);
    int res = 0, ed = -2e9;
    for (int i=0; i < n; i++){
        if (range[i].l > ed){
            res ++;
            ed = range[i].r;
        }
    }
    printf("%d", res);
    return 0;
}

排课 (不冲突排尽量多的课)

和上题一样, 上题选点的个数(有点的区间相互没有相交) = 这题的课程数

区间分组

区间分组, 每组内的区间两两没有交集, 要求组数尽量小. (合法的 → answer ≤ count)

  1. 每个区间按左端点从小到大排序
  2. 从前往后依次枚举每个区间
  • 判断能否放入现有的组中 L[i] > max_r
    • 不能, 新建一个组
    • 存在, 随便挑一个, 将其放入, 更新当前组的max_r
    • 最后分出的count个组, 每个都是相交的, 因此必须分开 → answer ≥ count
    • => answer = count
  1. 区间max_r可以用小根堆存储
 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

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N=100010;

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

int main(){
    scanf("%d", &n);
    for (int i=0; i < n; i++){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range+n);
    
    priority_queue<int, vector<int>, greater<int> > heap;
    for (int i=0; i<n; i++){
        auto r = range[i];
        if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else{
            int t = heap.top();
            heap.pop();
            heap.push(r.r);
        }
    }
    
    printf("%d", heap.size());
    return 0;
}

区间覆盖

给定一些小区间和一个大区间[start, end], 要求用尽量少的小区间去完全覆盖大区间.

  1. 将所有区间按左端点从小到大排序
  2. 从前往后依次枚举每个区间, 在所有能覆盖start的区间中, 选择右端点最大的那一个, 将start更新成这个右端点
    • 合法的 → answer ≤ count.
    • 反证法 → answer ≥ count. 假设answer < count, 找到第一个不一样的, 替换掉, 保持个数不变且依然合法.
    • answer = count.
 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 <algorithm>
#include <queue>

using namespace std;

const int N=100010;

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

int main(){
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i=0; i < n; i++){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range+n);
    
    int res = 0;
    bool success = false;
    for (int i=0; i < n; i++){
        int j=i, r=-2e9;
        while (j<n && range[j].l <= st){
            r = max(r, range[j].r);
            j++;
        }
        if (r < st){
            res = -1;
            break;
        }
        res ++;
        if (r >= ed) {
            success = true;
            break;
        }
        st = r;
        i = j-1;
    }
    if (!success) res = -1;
    printf("%d", res);
    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
26

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater<int>> heap;
    while(n--){
        int x;
        scanf("%d", &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);
    }
    printf("%d", res);
    return 0;
}