第25届宁波市中小学生程序设计竞赛(初中组)复赛第三题——插入排序_百...
发布网友
发布时间:2022-05-29 04:40
我来回答
共2个回答
热心网友
时间:2024-10-22 13:28
//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;
procedure 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.
热心网友
时间:2024-10-22 13:30
不会pascal,你自己调试吧。
readln(n);
for i:=1 to n do
begin
read(a[i]);
end;
for i:=2 to n do
begin
j = i - 1;
s = a[i];
while j > 0 and s < a[j] do
begin
a[j+1] = a[j];
end
a[j+1] = s;
end
热心网友
时间:2024-10-22 13:32
//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;
procedure 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.
热心网友
时间:2024-10-22 13:28
不会pascal,你自己调试吧。
readln(n);
for i:=1 to n do
begin
read(a[i]);
end;
for i:=2 to n do
begin
j = i - 1;
s = a[i];
while j > 0 and s < a[j] do
begin
a[j+1] = a[j];
end
a[j+1] = s;
end