不是VIP会员,不能显示答案
在后台新版,查看答案更方便。

题目解答

题目:
program xx2011_3;
const maxn=100000;
var
f:array[1..maxn]of longint;
stack:array[1..maxn,1..2]of longint;
n,i,j,h,t,last,x,s:longint;
begin
read(n);
for i:=1 to n do read(f[i]);
stack[1,1]:=1;
stack[1,2]:=n;
last:=2;
while last>1 do begin
last:=last-1;
h:=stack[last,1];
t:=stack[last,2];
i:=h;
j:=t;
x:=f[h];
while i<j do begin
while(i<j)and(f[j]<x) do j:=j-1;
if i<j then begin
f[i]:=f[j];
i:=i+1;
end;
while (i<j)and(f[i]>x) do i:=i+1;
if i<j then begin
f[j]:=f[i];j:=j-1;
end;
end;
f[i]:=x;
if(h<i-1) then begin
stack[last,1]:=h; stack[last,2]:=i-1;last:=last+1;
end;
if(i+1<t) then begin
stack[last,1]:=i+1;stack[last,2]:=t;last:=last+1;
end;
end;
s:=f[2]-f[1];
for i:=3 to n do s:=s+f[i]-f[i-1];
writeln(s);
end.
输入1:
3
20 10 30


输入2:
10
40 36 47 29 25 35 22 42 13 58
输出:-20
-45
考点: 0
分析:
解答: 排序!
s:=f[2]-f[1];
for i:=3 to n do s:=s+f[i]-f[i-1];
评论:
老师: