P1668 Cleaning Shifts S 题解

· · 题解

典型的区间覆盖问题，自然要用典型的贪心去解

思路不难想到，为了尽可能覆盖得多，要从覆盖时间最早的区间开始检查，而后每次尽可能覆盖得更远

所以需要按照左端点从小到大排序，而后如何实现剩余的部分就是工程问题了

大致而言：

我需要遍历所有左端点小于当前区间右端点的区间，而后找到其中那个右端点最大的区间

为什么一定是左端点小于当前右端点的区间呢？这很显然，如果左端点比当前右端点大，那中间肯定会有遗漏

所以我们需要一个循环

而所谓的“当前区间”是什么呢？这需要一个变量去指代，最简单的方法就是指代它的索引

索引显然不能大于n，能否等于这取决于你的输入，按照我的习惯因为从0开始所以索引不能大于等于n

另一方面还需要确保当前检索的区间的左端点始终小于目前的右端点+1

为什么是右端点+1呢？

以上就是循环的两个条件

while(r<n && cows[r].start<=cur){//cur为当前右端点+1
    rightest = max(rightest, cows[r].end);
    r++;
}

那么什么情况下我们可以断定覆盖必然失败呢？

也就是剩下的所有区间都无法覆盖到更远的点的时候，换句话说我们看了一圈发现rightest还比cur要小

此处做一个特殊判定输出-1就好

其他情况下，既然这个区间覆盖到了更远的点，那它自然是答案的一部分，ans++

再做一次特判，假设此时已经覆盖了最后的点，那么输出答案，return 0即可

两次特判筛过之后，现在我们的情况就是：我们覆盖到了更远的点，但我们还没有覆盖到终点

所以我们需要以目前的这个最远区间为基础进行下一次循环，故更新cur

遍历

cur = rightest+1

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
struct cow{
    int start,end;
}cows[25005];
int n,t; 
bool cmp(cow a, cow b){
    return a.start<b.start;
}
int main(){
    cin >> n >> t;
    for(int i=0;i<n;i++){
        cin >> cows[i].start >> cows[i].end;
    }
    sort(cows,cows+n,cmp);
    int cur = 1, ans = 0; 
    for(int i=0;;){
        int rightest = -1;
        while(i<n && cows[i].start<=cur){
            rightest = max(rightest, cows[i].end);
            i++;
        }
        if(rightest<cur)break;
        ans++;
        if(rightest>=t){
            cout << ans;
            return 0;
        }
        cur = rightest+1;
    }
    cout << -1 << endl;
    return 0;
}

尽可能捋清了代码的逻辑，然而还是有几个处理细节让我不太能接受：

1.真的要采用for(int i=0;;)这样丑陋的形式吗？我考虑过使用while，但是我发现外面的判断条件非常赘余，最后大多数情况下还是里面那个while在发挥作用，我试着把rightest<cur作为核心判断条件，但发现它无法在合适的位置跳出循环，ans++的位置也会变模糊

2.纯粹从逻辑上解释的话，cur=rightest+1这一点目的在于避免重复覆盖当前区间右端点，cows[i].start<=cur中等于的成分也是为了这个目标而服务的，但是我还是觉得哪里不对，或者单纯觉得这个“+1”有点麻烦

3.rightest<=cur作为一个判断条件算是合理的，可是是如何想到这一步的呢？鉴于给出的区间的端点中必然包括1和终点，所以覆盖问题只可能出在中间……它似乎是在以区间不断累积这样一种变化的角度看待问题，确定“在当前状态下我永远不可能覆盖到那个点”，因此这个判断是成立的……逻辑上我似乎理解了，但就是哪里不对