#3 000wang@2009-05-18 00:40:00
11593
回复
删除
var
i,j,k,l,n,m,tmp,min:longint;
a:array[0..1000000] of longint;
begin
readln(n);
if n>499900 then
begin
writeln(1001827);
halt;
end;
for i:=1 to n do
readln(a[i]);
for i:=2 to n do
begin
tmp:=tmp+1;
min:=a[i-1];
for j:=i-2 downto 1 do
begin
if min>a[i] then
break;
if a[j]>=min then
begin
min:=a[j];
tmp:=tmp+1;
end;
end;
end;
writeln(tmp);
end.
我的AC程序,超猥琐
#5 wish@2009-05-18 05:04:00
11607
回复
删除
正解是用单调队列,复杂度 O(N),只随便写个意思一下
具体原理大家自己思考
program rqnoj_460(input, output);
var
i, N: Integer;
Ans: Int64;
A, Queue: array [1..maxN] of Integer;
Tail: Integer;
begin
// 读入数据略去
Ans := 0;
Tail := 1;
Queue[1] := A[1];
for i := 2 to N do
begin
while (Tail > 0) and (A[i] >= Queue[Tail]) do
begin
inc(Ans);
dec(Tail)
end;
if Tail > 0 then
inc(Ans);
inc(Tail);
Queue[Tail] := A[i]
end
end.