题解 P7839 「Wdoi-3」夜雀 singing

· · 题解

被神仙slzs安利做了一下，可惜神仙slzs没能赛时切掉。

对于每一个鸟，我们可以处理出它左边最远能走到的点和右边能走到的最远的点，那么这个鸟能活动的范围就是一个区间。对于这个区间里面，如果有一个点的高度大于给出的时刻总数 t，那么这只鸟就是安全的，我们不用管了。对于不安全的鸟，我们要给它们放一些传送点，让它能够传到安全的地方。

首先，有一个传送点要放在一个高度大于给出的时刻总数 t 的位置，单独加上。可以发现，剩下的问题可以转化为：对于所有不安全的鸟的区间，放置最少的点使得所有区间都被覆盖，这是经典的最少点覆盖区间问题，可以用贪心解决。

我们把所有区间按左端点从小到大排序，然后贪心地选当前区间最远的点（右端点），如果这个区间的左端点大于上个区间的右端点，则说明需要再添加一个点，总点数加一即可，注意要处理一下有区间完全包含另一个区间的情况，这种情况只能取被包含的区间来算，我用了取 min 也可以解决这个问题。

回到处理每只鸟能走的区间的问题，如果单独考虑左右端点中的一个可以发现它具有单调不降，可以像马拉车类似的思想，如果之前的鸟能走到的最远的点小于等于当前鸟的位置，则暴力跑一遍跑出当前鸟的最远点并记录下来，如果之前的鸟能走到的最远点大于当前鸟的位置，则当前的鸟也一定可以走到那个最远点（因为走到最远点用掉的时间会比前一个点用时更少），所以直接从最远点开始跑暴力就行了。复杂度 \Theta(n+m)。

至此我们解决了这题，别忘了最后的答案加上最开始单独考虑的 1。

#include<bits/stdc++.h>
using namespace std;
template <class T>
inline T read(){
    T ans=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=ch=='-',ch=getchar();
    while(isdigit(ch)) ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return f?-ans:ans;
}
const int N=5e6+5;
int n,m,t,ans;
int a[N],p[N],sum[N],vis[N];
struct zfz{
    int l,r;
}line[N];
bool cmp(zfz x,zfz y){return x.l<y.l;}
int main(){
    n=read<int>(),m=read<int>(),t=read<int>();
    for(int i=1;i<=n;++i) a[i]=read<int>();
    for(int i=1;i<=m;++i) p[i]=read<int>();
    sort(p+1,p+1+m);
    int Max=0,T;
    for(int i=1;i<=m;++i){
        if(p[i]>Max) T=0,Max=p[i];
        else T=Max-p[i];
        while(T+1<a[Max+1]) ++T,++Max;
        line[i].r=Max;
    }
    Max=n;
    for(int i=m;i;--i){
        if(p[i]<Max) T=0,Max=p[i];
        else T=p[i]-Max;
        while(T+1<a[Max-1]) ++T,--Max;
        line[i].l=Max;
    }
    sort(line+1,line+1+m,cmp);
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+(a[i]>t);
    for(int i=1;i<=m;++i) vis[i]=sum[line[i].r]-sum[line[i].l-1]>0?1:0;
    int last=0;
    for(int i=1;i<=m;++i){
        if(vis[i]) continue;
        if(line[i].l>last) ++ans,last=line[i].r;
        else last=min(last,line[i].r);
    }
    if(!ans) puts("0");
    else printf("%d",ans+1);
    return 0;
}