|
我们可以开一个一维数组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);
}
|
