|
|
思路：
用线段树维护所有线段的分布。
新增加一个fence的时候，将fence的范围[a, b]插入线段树，节点的值为fence的编号，即高度。
那么fence上的某一点就是树的叶子了，从叶子往上一直到根节点的路径中节点的最大值，
就是从fence上的这一点垂直掉下去后，碰到的一个fence了。
这样，我们就可以在O(lgN)时间内知道，从一个fence的端点掉下去会碰到哪个fence了。 不然从后往前一个个找就是O(N)复杂度了。同时N也很大，必然超时。 同时也可以发现，一个fence保存两个值用作动态规划就好了，向左、右走之后，掉到其他fence上面，然后回到基地所用的最短路径。 推的方法很简单，掉到其他fence上面之后，看下是向左走距离短还是向右走距离短。就行了。 这个代码跑到400ms。
 #include <stdio.h>
#define MAX_N 50032
#define MAX_R 100032
  struct  {
 int a, b;
 } dp[MAX_N], fences[MAX_N];
int N, S, tree[MAX_R*16];
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline int abs(int a)
{
return a > 0 ? a : -a;
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
void insert(int idx, int start, int end, int left, int right, int val)
{
int mid;
  if (start == left && right == end) {
tree[idx] = val;
return ;
 }
mid = (start + end) / 2;
if (right <= mid)
insert(idx*2, start, mid, left, right, val);
else if (left > mid)
insert(idx*2+1, mid + 1, end, left, right, val);
else {
insert(idx*2, start, mid, left, mid, val);
insert(idx*2+1, mid + 1, end, mid + 1, right, val);
}
}
int query(int idx, int start, int end, int pos)
{
int val, mid;
if (start == pos && end == pos)
return tree[idx];
mid = (start + end) / 2;
if (pos <= mid)
val = query(idx*2, start, mid, pos);
else
val = query(idx*2+1, mid + 1, end, pos);
return max(val, tree[idx]);
}
__inline int calc_min(int i, int pos)
{
if (!i)
return abs(pos - MAX_R);
return min(pos - fences[i].a + dp[i].a, fences[i].b - pos + dp[i].b);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &S);
S += MAX_R;
for (i = 1; i <= N; i++) {
scanf("%d%d", &fences[i].a, &fences[i].b);
fences[i].a += MAX_R;
fences[i].b += MAX_R;
dp[i].a = calc_min(query(1, 0, MAX_R*2, fences[i].a), fences[i].a);
dp[i].b = calc_min(query(1, 0, MAX_R*2, fences[i].b), fences[i].b);
insert(1, 0, MAX_R*2, fences[i].a, fences[i].b, i);
}
printf( "%d\n",
min(S - fences[N].a + dp[N].a, fences[N].b - S + dp[N].b)
);
return 0;
}
|