题解 P1081 【开车旅行】
The_Dark_Knight · · 题解
改了半天的细节，把粗心的地方都改过来了。
最容易想到的当然是模拟，A、B按照自己的方法一步步走，但是稍微算一算就知道肯定会超时
再想到优化一点点，将每个点距离最近、第二近的点预处理出来，在后面的询问中直接调用，显然又要快一点点
能够发现，A、B的走法是机械化、有顺序规律的，那么我们不妨把A、B各走一次看做一次行动，然后用倍增的方法来“跳着走”，这样就没问题了。
那么具体说说：
1.关于预处理最近及第二近的点。首先我们知道必须是由编号小的点通向大的点（小的点在西边），我们又可以知道，将高度排序一次之后，对于排好序的高度序列里面来说，i点最近及第二近的点必然是i-1、i-2、i+1、i+2中的两个，考虑到之前所说的必须由编号小的通向编号大的，所以在排序过程中还需要存储初始编号。然而如果每一次都枚举左右两边第一个或者第二个小于或者大于他的点，最坏的情况可能会达到O（n^2），显然也不靠谱，那么我们考虑用链表来优化一下。pre[i]为第一个小于i且编号大于i的点，next[i]为第一个大于i且编号大于i的点，我们从编号1开始做起，找到最大及第二大的点之后，把1从链表中去掉，把1的两边连接起来，这样子的话在做后面的点时就不会再找到1这个点。重复对每个编号操作一次，就可以求出每个点最近及第二近的点。（果然解释起来还是很麻烦，具体参照代码吧）
2.倍增，f[i,j]表示从i点出发走2^j次行动所到达的点（每次行动包括A走一次B走一次），sa[i,j]表示A所走的路程，sb同理。但是我们可以想到，经过若干次行动之后，也许A还能再走，但是B不能再走了，这个时候特判一下就好。
3.对于第一问就枚举求解就好，第二问也可以一个个回答
type node=record
h,next,pre:longint;
end;
origin=record
num,hh:longint;
end;
var a,b:array[1..100000] of longint;
st:array[1..100000] of origin;//用来排序
fi:Array[0..100000] of node;//fi存储排序后的编号对应的原编号
f:array[0..100005,0..20] of longint;
sa,sb:array[0..100005,0..20] of int64;
i,j,k,m,n,p,t,l,r,s,min,cmin,mp,cmp:longint;smin:double;ta,x,tb:int64;
procedure sort(l,r: longint);
var
i,j,x: longint;y:origin;
begin
i:=l;
j:=r;
x:=st[(l+r)>>1].hh;
repeat
while st[i].hh<x do
inc(i);
while x<st[j].hh do
dec(j);
if not(i>j) then
begin
y:=st[i];
st[i]:=st[j];
st[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
procedure run(now:longint);//倍增
var i,j,k:longint;
begin
j:=now;
ta:=0;tb:=0;
for k:=20 downto 0 do
if (ta+sa[now,k]<=x-tb-sb[now,k])and(f[now,k]<>0)and(sa[now,k]<>0)and(sb[now,k]<>0) then
begin
inc(ta,sa[now,k]);
inc(tb,sb[now,k]);
now:=f[now,k];
end;
if a[now]<>0 then
begin
if ta+tb+abs(fi[a[now]].h-fi[now].h)<=x then
ta:=ta+abs(fi[a[now]].h-fi[now].h);
end;
if tb<>0 then
begin
if ta/tb<smin then begin p:=j;smin:=ta/tb;end;
end else if smin=maxlongint then p:=j;
end;
begin
readln(n);
for i:=1 to n do
begin
read(st[i].hh);
st[i].num:=i;
end;
sort(1,n);
l:=st[1].num;r:=st[n].num;
for i:=1 to n do
begin
fi[st[i].num].h:=st[i].hh;
if i<n then fi[st[i].num].next:=st[i+1].num;
if i>1 then fi[st[i].num].pre:=st[i-1].num;
end;
fi[0].h:=maxlongint div 2;
for i:=1 to n do
begin
min:=maxlongint;
cmin:=maxlongint;
if i<>l then
begin
if abs(fi[i].h-fi[fi[i].pre].h)<min then begin mp:=fi[i].pre;min:=abs(fi[i].h-fi[fi[i].pre].h);end;
if abs(fi[i].h-fi[fi[fi[i].pre].pre].h)<cmin then begin cmp:=fi[fi[i].pre].pre;cmin:=abs(fi[i].h-fi[fi[fi[i].pre].pre].h);end;
end;
if i<>r then
begin
if abs(fi[i].h-fi[fi[i].next].h)<min then begin cmp:=mp;cmin:=min;mp:=fi[i].next;min:=abs(fi[i].h-fi[fi[i].next].h);end else
if abs(fi[i].h-fi[fi[i].next].h)<cmin then begin cmp:=fi[i].next;cmin:=abs(fi[i].h-fi[fi[i].next].h);end;
if abs(fi[i].h-fi[fi[fi[i].next].next].h)<cmin then begin cmp:=fi[fi[i].next].next;cmin:=abs(fi[i].h-fi[fi[fi[i].next].next].h);end;
end;
a[i]:=cmp;
b[i]:=mp;
fi[fi[i].pre].next:=fi[i].next;
fi[fi[i].next].pre:=fi[i].pre;
end;
for i:=1 to n-2 do
begin
f[i,0]:=b[a[i]];
sa[i,0]:=abs(fi[a[i]].h-fi[i].h);
sb[i,0]:=abs(fi[b[a[i]]].h-fi[a[i]].h);
end;
k:=trunc(ln(n)/ln(2));
for j:=1 to k do
for i:=1 to n do
f[i,j]:=f[f[i,j-1],j-1];
for j:=1 to k do
for i:=1 to n do
begin
sa[i,j]:=sa[i,j-1]+sa[f[i,j-1],j-1];
sb[i,j]:=sb[i,j-1]+sb[f[i,j-1],j-1];
end;
readln(x);
smin:=maxlongint;
for i:=1 to n do
run(i);
writeln(p);
readln(m);
for i:=1 to m do
begin
readln(s,x);
run(s);
writeln(ta,' ',tb);
end;
end.