P1668 [USACO04DEC] Cleaning Shifts S 题解

· · 题解

题面大意

给你一个 t，一个 n，和 n 个区间 [s[i],e[i]]。 让你求一个数 ans，使得在这 n 个区间中取 ans 个区间 [ss[i],ee[i]]，能够令 \bigcup_{i=1}^{ans} [ss[i],ee[i]]=[1,t]，且 ans 要尽可能小。

分析

首先，因为因为它要令几个区间的并集为 [1,t]。

所以，我们考虑贪心求覆盖当前区间 [1,k] 的最小的区间数，并记录区间数最小时区间并的最大右端点。

当 k 增大时，如果最大右端点比 k 小，那么求 \max_{i=1}^{n} e[i] ,s[i]<=最大右端点。

显然，当前区间并与该选定区间合并等价于令当前区间并的最大右端点与该选定区间右端点取最大值。

所以，我们直接把当前区间并的最大右端点赋值为该选定区间右端点取最大值。

而，若赋值后区间并的最大右端点仍小于 k ，那么可得知求不出 ans，所以直接输出负一。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+5;
int n,t,la,ma[N],maa,ans;
struct node{
    int s,e;
}a[N];//给定区间
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>t;la=1;
    for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].e,ma[a[i].s]=max(ma[a[i].s],a[i].e);//ma[i]:以i为左端点区间的最大右端点
    for(int i=1;i<=t;i++){
        if(la<i) cout<<-1,exit(0);//若无解，输出-1
        maa=max(maa,ma[i]);//求选定区间右端点
        if(la==i) la=maa+1,ans++;//提前一步赋值为选定区间右端点，la是最大右端点+1
    }
    if(la<=t) cout<<-1,exit(0);//同上
    cout<<ans;
    return 0;
}

该算法不用快排，所以不带 \log，时间复杂度 O(n)，但在该题中时间还是那些带 \log 的快（可能时数据太水了）。