【题意】
有n个平台,每个有一个宽度和不同的高度,现向高度最低的平台以每分钟一单位的速度注水,求各平台什么时刻水面高于平台顶1单位距离
【输入】
第一行n
接下来n行每行两个整数表示宽度和高度
【输出】
n行,每行一个数字表示这个平台什么时刻高于平台顶一单位距离
模拟,利用链表存储
program poj3658; var n,i,j,k:longint; now:int64; ans,last,next,w,h:array [0..100001] of int64; begin read(n); w[0]:=0; h[0]:=maxlongint; w[n+1]:=0; h[n+1]:=maxlongint; k:=0; for i:=1 to n do begin read(w[i],h[i]); last[i]:=i-1; next[i-1]:=i; next[i]:=i+1; last[i+1]:=i; if h[i]<h[k] then k:=i; end; now:=0; for j:=1 to n do begin while (h[last[k]]<h[k])or(h[next[k]]<h[k]) do if h[last[k]]<h[k] then k:=last[k] else k:=next[k]; ans[k]:=now+w[k]; last[next[k]]:=last[k]; next[last[k]]:=next[k]; if h[last[k]]<h[next[k]] then begin now:=now+w[k]*(h[last[k]]-h[k]); w[last[k]]:=w[last[k]]+w[k]; k:=last[k]; end else begin now:=now+w[k]*(h[next[k]]-h[k]); w[next[k]]:=w[next[k]]+w[k]; k:=next[k]; end; end; for i:=1 to n do writeln(ans[i]); end.