寧波市第25屆中小學生程序設計競賽

㈠ 第25屆寧波市中小學生程序設計競賽（初中組）復賽第三題——插入排序

//O(n*lgmaxm)
const maxn=100000;maxm=20000;
var a:array[1..maxn]of longint;
c,lowbit:array[1..maxm]of longint;
n,i,j,sum,max,tmp:longint;

function findmax(i:longint):longint;
var max:longint;
begin
max:=0;
while i>0 do begin
if max<c[i] then max:=c[i];
i:=i-lowbit[i];
end;
findmax:=max;
end;

procere fill(i,x:longint);
begin
while i<=maxm do begin
if c[i]<x then c[i]:=x;
i:=i+lowbit[i];
end;
end;

begin
assign(input,'insert.in');reset(input);
assign(output,'insert.out');rewrite(output);
for i:=1 to maxm do lowbit[i]:=i and (i xor (i-1));
read(n);
for i:=1 to n do read(a[i]);
sum:=0;
for i:=1 to n do sum:=sum+a[i];
fillchar(c,sizeof(c),0);
max:=0;
for i:=1 to n do begin
tmp:=findmax(a[i]);
tmp:=tmp+a[i];
if max<tmp then max:=tmp;
fill(a[i],tmp);
end;
writeln(sum-max);
close(output);close(input);
end.