9.16

[Ryanlyt]

贪心

代码简单，证明难

区间问题

区间选点

1、将每个区间按右端点从小到大排序 2、从前往后依次枚举每个区间（如果当前区间中已经包含点，则直接pass；否则，选择当前区间的右端点）

#include <bits/stdc++.h>

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\n",res);

    return 0;
}

最大不相交区间数量

#include <bits/stdc++.h>

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};
    }

    int ed = -2e9, res = 0;
    for(int i = 0; i < n; i++){
        if(range[i].l > ed){
            res++;
            ed = range[i].r;
        }
    }

    printf("%d\n",res);

    return 0;
}

区间分组

什么时候考虑左端点，什么时候右端点：经验、积累

动态的维护最小值：可以用小根堆（优先队列）来做

区间覆盖

#include <bits/stdc++.h>

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、从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择一个右端点最大的区间，并把start更新成右端点的的最大值

[Ryanlyt]

Huffman树

合并果子

#include <bits/stdc++.h>

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;
}

[Ryanlyt]

排序不等式

排队打水

[Ryanlyt]

绝对值不等式

货仓选址

[Ryanlyt]

推公式

耍杂技的牛