2020牛客NOIP赛前集训营-提高组（第二场）T4移动

2020牛客NOIP赛前集训营-提高组（第二场）T4移动

比赛时T3调了2个多小时 太菜了，导致没时间写T4，写了个暴力就交上去了，结果稳稳爆零（后来看变成了15?
本题解写了一半被手滑关掉了，不得不重写

进入正题，首先讲一下题意，你要从0走到n+1，其中有n个闸门，在一些时间段会关闭，每一秒可以向左，向右，不动，问最短时间（当x闸门t时刻打开，相邻的y闸门t+1时刻打开，就可以在时刻t从x移到y）
为了便于操作，将关闭时间转换成打开时间
这样一来，总共会有约2n个时间段，把它们看作新的时刻，此时每个新的时刻都对应着一个闸门（以下简称时刻）
我们记状态表示在时刻t，走到闸门p（t和p其实是对应的），当前所用时间（时刻t中的具体时间点）为x
考虑转移，当时，可以向左走，则下一个状态形如（为什么是x'而不是x+1？这是因为不一定恰好你刚到p就能走到p-1，可能需要等待一些时间）
如图：（nxt在这里表示p-1，同理也可以表示p+1，即下一个位置）

当时刻包含到中的任何一个时间点时，即可转移（中间可能会需要等待时间）
向右走同理

实现时，可以用一个堆，每次取出x最小的状态，进行转移
为了防止超时，我们记录在每个时刻到达每个闸门最短时间，当当前状态的时间大于当前最短时间时，不需要转移（一个时刻内时间越短越优，因为一个时刻内，闸门都是开的，可以等待，到达时间越短，转移可能越多）

code:（中间的注释会讲解一些细节）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
const int maxn=100020, INF=2000000000;

struct pj{
    int l, r; 
    int operator<(const pj& rhs) const {return l<rhs.l||l==rhs.l&&r<rhs.r;}
};
int n, m, b[maxn<<1], f[maxn<<1];
vector<pj> a[maxn], v;
struct tg{
    int t, p, x;
    int operator>(const tg& rhs) const {return x>rhs.x;}
};
priority_queue<tg, vector<tg>, greater<tg> > q;

int cmp(pj a, pj b) {return a.r<b.r;}

void move(tg u, int nxt) {//将状态u转移到nxt的位置
    vector<pj>::iterator it=upper_bound(a[nxt].begin(), a[nxt].end(), (pj){u.x, u.x}, cmp);
//第一个包含x+1的时刻
    while(it!=a[nxt].end()&&it->l<a[u.p][u.t-b[u.p]].r+2) {//保证时刻至少包含x+1到r+1中的一个
        int p=it-a[nxt].begin()+b[nxt];
        if(f[p]>max(it->l, u.x)+(it->l<=u.x)) {
//当it->l<=x时，max为x，但因为时间点为x时才到达，至少要到x+1才能到到nxt，所以加1
            q.push((tg){p, nxt, max(it->l, u.x)+(it->l<=u.x)});
            f[p]=min(f[p], max(it->l, u.x)+(it->l<=u.x));
        }    
        ++it;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1, x, l, r; i<=m; ++i) {
        scanf("%d%d%d", &x, &l, &r);
        a[x].push_back((pj){l, r});
    }
    a[0].push_back((pj){0, INF}); b[0]=1;
    a[n+1].push_back((pj){0, INF});
    for(int i=1; i<=n; ++i) {//将关闭时间转化成打开时间
        sort(a[i].begin(), a[i].end());
        while(v.size()) v.pop_back();
        if(a[i].size()) {
            v.push_back((pj){0, a[i][0].l-1});
            for(int j=0; j<a[i].size()-1; ++j)
                v.push_back((pj){a[i][j].r+1, a[i][j+1].l-1});
            v.push_back((pj){a[i][a[i].size()-1].r+1, INF});
            a[i]=v;
        } else a[i].push_back((pj){0, INF});
        b[i]=b[i-1]+a[i-1].size();
    }
    b[n+1]=b[n]+a[n].size();
//    for(int i=0; i<=n+1; ++i, puts(""))
//        for(int j=0; j<a[i].size(); ++j) printf("(%d, %d)", a[i][j].l, a[i][j].r);
//    for(int i=1; i<=n; ++i) printf("%d ", b[i]); puts("");
    q.push((tg){1, 0, 0});
    memset(f, 0x3f, sizeof f); f[1]=0;
    while(!q.empty()) {
        tg u=q.top(); q.pop();
//        printf("%d %d %d\n", u.t, u.p, u.x);
//        for(int i=1; i<=b[n+1]; ++i) printf("%d ", f[i]); puts("");
        if(u.p>0) move(u, u.p-1);
        if(u.p<n+1) move(u, u.p+1);
    }
    printf("%d", f[b[n+1]]);
    return 0;
}

由于太菜，可能会有些错误，如果发现，欢迎指出