|
|
思路：
用線段樹維護所有線段的分布。
新增加一個fence的時候，將fence的范圍[a, b]插入線段樹，節(jié)點的值為fence的編號，即高度。
那么fence上的某一點就是樹的葉子了，從葉子往上一直到根節(jié)點的路徑中節(jié)點的最大值，
就是從fence上的這一點垂直掉下去后，碰到的一個fence了。
這樣，我們就可以在O(lgN)時間內(nèi)知道，從一個fence的端點掉下去會碰到哪個fence了。 不然從后往前一個個找就是O(N)復(fù)雜度了。同時N也很大，必然超時。 同時也可以發(fā)現(xiàn)，一個fence保存兩個值用作動態(tài)規(guī)劃就好了，向左、右走之后，掉到其他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;
}
|