题解 P2980 【[USACO10FEB]覆盖的围栏Covering the Corral】

· · 题解

这是一道模拟题 思路：排序优化，模拟放置。

HINT：先把被别人覆盖的丢掉。环？复制一遍当做序列来做。对每个壁纸求出能接在它后面的右端点最大的。（怎么求？）那之后咋办啊（掀桌） 我会！枚举作为起点的牛，然后不断地往后跑直到覆盖一整圈！ ......n元环了解一下？ 把牛看作点，每个点有且只有一条出边...基环内向树！ 点权为壁纸长度，边权为增加的有效长度。 只要起点点权+各边权和>=C就好了。 类似于two pointer，随着起点往后跳，终点也随着往后跳。 可惜的是不管是正向还是反向复杂度都好像是错的。。 。

首先把被完全覆盖的围栏去掉，剩下的按左端点升序排序。那么右端点肯定也是升序的了。。然后计算出每段围栏，它接下去一段围栏可达到的最远距离。枚举起点，贪心地一段一段接下去就可得到该起点的最优解。

直接这样做显然会T。。

正解

换个方向...考虑某个答案啥时候会被计算到。 显然不管是啥答案，肯定有条跨过环的边。 枚举那条边...然后呢？总不能直接跑吧对每个点x预处理出f[x],pos[x]：以x为起点，一直跳到 即将跨环 (再走一步就跨环了)的时候，走了几条边，停在哪里。枚举跨环的初始边(x,y)，之后y直接跑到pos[y]，然后稍微判断一下。

AC代码 

#include<iostream>
#include<algorithm>
using namespace std;
const int N=200001;
const int INF=0x3f3f3f;
struct node{
    int l,r;
}a[N];
int nxt[N],pos[N],jump[N],tmpcos[N];
int i,j,L,n,m,ans,k;
bool cmp(node x,node y){
    return x.l==y.l?x.r>y.r:x.l<y.l;//排序了解一下
}
void get(int x){//得到当前牛所能到达的最远点
    if(jump[x]) return;

    if(a[x].r>=L){
        jump[x]=x;
        tmpcos[x]=0;
    }else{
        get(nxt[x]);
        jump[x]=jump[nxt[x]];
        tmpcos[x]=tmpcos[nxt[x]]+1;
    }
}
int main(){
    cin>>L>>n;
    for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r,a[i].r+=a[i].l;
    sort(a+1,a+n+1,cmp);
    int mx=-1,tmp=0;
    for(int i=1;i<=n;i++)//缩牛操作
      if(a[i].r>mx) {
          a[++tmp]=a[i];
          mx=a[i].r;
      }
    n=tmp;
    tmp=0;
    for(int i=1;i<=n;i++){//计算pos
        nxt[i]=nxt[i-1];
        for(;tmp<n&&a[tmp+1].l<=a[i].r;tmp++);
        if(tmp==i) nxt[i]=0;
        else{
            nxt[i]=tmp;
            pos[i]=a[tmp].r;
        }
        //cout<<nxt[i]<<endl;
    }
    int tmpsum,now;//tmpsum:计算牛的总数
    ans=INF;
    for(int i=1;i<=n;i++){
        if(!jump[i]) get(i);
        tmpsum=tmpcos[i]+1;
        now=jump[i];
        while(nxt[now]&&a[now].r<a[i].l+L&&tmpsum<ans){
            now=nxt[now];
            tmpsum++;
        }
        if(a[now].r>=a[i].l+L&&tmpsum<ans) ans=tmpsum;
    }
    cout<<ans<<endl;
    return 0;
}