P1668 题解

Greenzhe · 2023-07-12 21:19:04 · 题解

看到题解区没有贪心解法，来交一发。蒟蒻第一次做证明，如有勘误，敬请指教。

该题的本质是从 n 个区间里选择一些区间，在这些区间能覆盖 [1,t] 内所有整数点的前提下，使得选择的区间个数最小。

算法流程：

1. 将所有区间按左端点从小到大排序。

2. 设 st 为当前最靠左的没有被覆盖的点。枚举每个区间，在所有能覆盖 st 的区间中，挑一个右端点最大的作为当前决策。然后更新 st。

3. 如果找不到能覆盖 st 的区间，则原问题无解。

利用双指针实现算法。

#include <bits/stdc++.h>
using namespace std;

struct segment{
    int l,r;
    bool operator<(const segment &x) const{
        return l<x.l;
    } // 重载小于号，用于 sort()。也可以用 cmp() 函数实现同样功能。
}range[25005];

int main(){
    int n,ed;
    scanf("%d%d",&n,&ed);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&range[i].l,&range[i].r);
    sort(range+1,range+n+1);
    int st=1,ans=0;
    for(int i=1,j=1;i<=n;){
        int r=0;
        while(j<=n&&range[j].l<=st){ // 左端点要 <= st，即该区间能覆盖 st 
            r=max(r,range[j].r); // 找右端点最大的
            j++;
        }
        if(r<st) break; // 找不到能覆盖 st 的区间
        ans++;
        if(r>=ed){ // 有解，输出
            printf("%d\n",ans);
            return 0;
        }
        st=r+1;i=j;
    }
    printf("-1\n");
    return 0;
}

证明：

参考闫学灿《算法基础课》。

只考虑有解的情况。

• 正确性：由于我们每次选择的左端点 \le 上次选择的右端点，所以能保证任意两个区间都是连接的。所以每个整数点都一定会被覆盖到。

• 最优性：假设最优解与该算法得出的解有部分区间选择不同。由于该算法中每次选择右端点最大的区间，所以一定能够覆盖更多的点。如果我们把最优解中选择的区间换成该算法选择的区间，显然答案不会更劣。

综上所述，以上贪心算法能得出最优解。