首先，很容易想到Dp。設f[i][0]表示第i個柵欄走左邊的最短路，f[i][1]表示第i個柵欄走右邊的最短路。
所以，我們要找一個剛好在第i個柵欄的左右邊界下面的柵欄。如圖所示：
則有：
f[i][0] = min(f[k][0] + |Left[i] - Left[k]| , f[k][1] + |Left[i] - Right[k]| )
f[i][1] = min(f[j][0] + |Right[i] - Left[j]| , f[j][1] + |Right[i] - Right[j]| )
那么，該怎樣求k和j呢？
很容易想到開一個數組，從小到大覆蓋。但這樣的時間復雜度是O（n^2）的。用線段樹區間修改，單點查詢就可以了。
附上程序：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <bitset>
#include <fstream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctime>
#include <deque>
#include <vector>
#include <complex>
#include <utility>
using namespace std;
typedef long long LL;
#define INF 0x3fffffff
#define Maxn 100010int num[Maxn<<1];
int f[Maxn][2];int n,m;int a[Maxn],b[Maxn];#define L(u) u<<1
#define R(u) u<<1|1struct Tnode{int l,r;bool isset;int set;
};
Tnode tr[Maxn<<3];void build(int u,int l,int r)
{tr[u].l = l; tr[u].r = r;tr[u].isset = true; tr[u].set = 0;if(l<r){int mid = (l+r)>>1;build(L(u),l,mid);build(R(u),mid+1,r);}
}void pushdown(int u)
{if(tr[u].isset){tr[L(u)].isset = tr[R(u)].isset = true;tr[L(u)].set = tr[R(u)].set = tr[u].set;tr[u].isset = tr[u].set = 0;}
}void update(int u,int l,int r,int val)
{if(l<=tr[u].l && tr[u].r<=r){tr[u].isset = true;tr[u].set = val;return;}pushdown(u);int mid = (tr[u].l+tr[u].r)>>1;if(mid>=l) update(L(u),l,r,val);if(mid<r) update(R(u),l,r,val);
}int query(int u,int p)
{if(tr[u].l==tr[u].r)return tr[u].set;pushdown(u);int mid = (tr[u].l+tr[u].r)>>1;if(p<=mid) return query(L(u),p);else return query(R(u),p);
}int main()
{ scanf("%d%d",&n,&m);build(1,1,Maxn<<1);a[n+1] = b[n+1] = m;for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);int k1,k2;for(int i=1;i<=n+1;i++){k1 = query(1,a[i]+100005);k2 = query(1,b[i]+100005);f[i][0] = min(f[k1][0]+abs(a[i]-a[k1]),f[k1][1]+abs(a[i]-b[k1]));f[i][1] = min(f[k2][0]+abs(b[i]-a[k2]),f[k2][1]+abs(b[i]-b[k2]));if(a[i]+1<b[i])update(1,a[i]+100005+1,b[i]+100005-1,i);}printf("%d\n",f[n+1][0]);return 0;
}
