我們可以開一個一維數組w[]，數組下標就是區間的端點值，cow剛開始在w[s]處。碰到一個區間後，我們看這個區間會覆蓋多少個值（實際就是到前面區間的端點所花的步數），枚舉這些值更新當前區間兩個端點值，枚舉完後，把覆蓋的值刪掉，添加這兩個新的端點值，區間外的值不用考慮。最後在從小到大枚舉這些端點值加上距離原點的距離即為答案，當然要從這些值中選擇最小的。
這其中涉及到刪除區間覆蓋的值和添加兩端點的值。如果用數組來做，最壞情況每次都是O（n），鏈表每次遍歷也會比較浪費時間。
這裡就選擇線段樹了。線段樹刪除和添加是logn，每次刪除的次數依賴剩余的端點，而每個端點最多被添加一次，刪除一次，所以復雜度為2*N*logL，L為區間最大距離。
PS：悲了個劇，用鏈表來做，500ms過了，而且代碼也短
線段樹，1500ms過，而且代碼量多了幾乎1倍
。。。。。。。。
先看鏈表代碼：
[cpp]
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <list>
using namespace std;
#define MP make_pair
#define x first
#define y second
const int INF = 0x3f3f3f3f;
const int maxn = 100010;
typedef pair<int, int> pii;
list<pii> p;
list<pii>::iterator it;
int w[maxn][2];
inline int f(int v)
{
return v >= 0 ? v : -v;
}
int main()
{
int n, s;
int l, r;
scanf("%d %d", &n, &s);
for(int i = 0; i < n; i++) scanf("%d %d", &w[i][0], &w[i][1]);
p.push_back(MP(0, s));
for(int i = n - 1; i >= 0; i--){
l = w[i][0], r = w[i][1];
int ll = INF, rr = INF;
for(it = p.begin(); it != p.end(); ){
if(l <= it->y && it->y <= r){
ll = min(ll, it->x + f(it->y - l));
rr = min(rr, it->x + f(it->y - r));
it = p.erase(it);
}else if(it->y > r)
break;
else it++;
}
if(ll < INF){
p.insert(it, MP(ll, l));
p.insert(it, MP(rr, r));
}
}
int ans = INF;
for(it = p.begin(); it != p.end(); it++){
ans = min(ans, it->x + f(it->y));
}
printf("%d\n", ans);
}
然後線段樹代碼：
[cpp]
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int INF = 0x3f3f3f3f;
const int maxn = 200010;
typedef pair<int, int> pii;
int cover[maxn << 2], MinV[maxn << 2], P[maxn << 2];
int w[maxn][2];
void PushUp(int rt)
{
MinV[rt] = MinV[rt << 1];
P[rt] = P[rt << 1];
if(MinV[rt] > MinV[rt << 1 | 1]){
MinV[rt] = MinV[rt << 1 | 1];
P[rt] = P[rt << 1 | 1];
}
}
void update(int p, int c, int l, int r, int rt)
{
if(l == r) {
MinV[rt] = c;
P[rt] = l;
return ;
}
int m = (l + r) >> 1;
if(p <= m) update(p, c, lson);
else update(p, c, rson);
PushUp(rt);
}
pii query(int L, int R, int l, int r, int rt)
{
if(L <= l && r <= R) return pii(MinV[rt], P[rt]);
int m = (l + r) >> 1;
pii u(INF, 0), v;
if(L <= m) {
v = query(L, R, lson);
if(u.first > v.first) u = v;
}
if(m < R) {
v = query(L, R, rson);
if(u.first > v.first) u = v;
}
PushUp(rt);
return u;
}
inline int f(int x)
{
return x >= 0 ? x : -x;
}
int main()
{
int n, s;
int L = INF, R = -INF;
int l, r;
memset(MinV, 0x3f, sizeof(MinV));
scanf("%d %d", &n, &s);
for(int i = 0; i < n; i++){
scanf("%d %d", &w[i][0], &w[i][1]);
L = min(L, w[i][0]);
R = max(R, w[i][1]);
}
update(w[n - 1][0], f(s - w[n - 1][0]), L, R, 1);
update(w[n - 1][1], f(s - w[n - 1][1]), L, R, 1);
for(int i = n - 2; i >= 0; i--){
l = w[i][0], r = w[i][1];
int ll = INF, rr = INF;
while(true){
pii u = query(l, r, L, R, 1);
if(u.first == INF) break;
ll = min(ll, u.first + f(u.second - l));
rr = min(rr, u.first + f(u.second - r));
update(u.second, INF, L, R, 1);
}
update(l, ll, L, R, 1);
update(r, rr, L, R, 1);
}
int ans = INF;
for(int i = L; i <= R; i++){
pii u = query(i, i, L, R, 1);
ans = min(ans, u.first + f(u.second));
}
printf("%d\n", ans);
}
