526互联

贪心选点问题

发布时间 2024-01-07 21:52:11作者: TomLove

贪心

image-20240107212146868

贪心区间选点

看了很多证明，感觉不是很透彻，根据我自己的理解写了这篇题解

ans 表示最优解 cnt 表示所有解中的一个

现在需要证明以下不等式

1） ans <= cnt

2） ans >= cnt

1） 的证明

因为 ans 是所有的解中的最优解（也就是最小的解） 而 cnt 是所有解的区间中的一个解 这个解的集合的最小值当然小于等于解集合中的所有情况

2）证明

我们先根据 1.将每个区间按照右端点进行排序 如果所有区间都不相交 没枚举一个区间都需要 增加一个点， 这是的一般解 cnt 就是所有解的最小值， 因为 cnt 是所有解的最小值， 当然小于等于 解的区间中的所有值。 ans >= cnt 的证

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;

// 定义一个结构体存放区间端点
struct Range{
    int l, r;
    // 重载一下方法
    bool operator< (const Range &W)const{
        // 根据 r 从小到大进行排序
        return r < W.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d%d", &range[i].l, &range[i].r);
    
    sort(range, range + n);
    
    int res = 0, ed = -2e9; // -2e9 表示无穷小
    // 循环枚举每一个区局
    for(int i = 0; i < n; i++)
        if(ed < range[i].l){
            // 如果当前的点不在当前枚举的区间内，在添加一个点
            // 添加的点为当前区间的右端点
            res ++ ;
            ed = range[i].r;
        }
        
    printf("%d", res);
    
    return 0;
}