#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.