P1668 [USACO04DEC] Cleaning Shifts S 题解

· · 题解

题面解释：

最小线段覆盖，段点不要求相交。

思路分析：

值域只有 10^6 的大小，我们直接开桶 to_i 维护从此处出发最远覆盖到哪里。前缀最大一下就可以得出在此之前开始的线段最远覆盖到哪里。

从 1 开始跳，每次跳到 to_i+1 （若拓展到要求相交不 +1 即可），并将答案加 1。若覆盖到最远的地方还没现在大，显然无解，无法再往后覆盖。若跳到的地方超过了 t，则完成覆盖。

这应该是最简洁的做法了吧，时间复杂度 O(n+t)。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int n,t,to[1000010];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>t;
    for(int i=1,x,y;i<=n;i++)
        cin>>x>>y,to[x]=max(to[x],y);
    for(int i=1;i<=t;i++)
        to[i]=max(to[i],to[i-1]);
    int now=1,ans=0;
    while(now<=t){
        if(to[now]<now){ans=-1;break;}
        now=to[now]+1,ans++;
    }cout<<ans;
    return 0;
}