讨论 / 最后一点超时 求解决方案
L.Lawliet 2010-11-14 23:16:00
点我顶贴 收藏 删除
const maxn=30000;

var f:array[0..maxn]of longint;

a:array[0..maxn]of longint;

i,j,k,m,n,t:longint;

ans:longint;

function find(l,r,k:longint):longint;

var mid:longint;

begin

while l<=r do

begin

mid:=(l+r)>>1;

if f[mid]=k then

begin

while f[mid]=k do inc(mid);

exit(mid);

end

else

if f[mid]>k then r:=mid-1 else l:=mid+1;

end;

exit(l);

end;

{main}

begin

readln(n);

for i:=1 to n do

readln(a[i]);

t:=0;

for i:=1 to n do

begin

j:=find(1,t,a[i]);

if j>t then inc(t);

f[j]:=a[i];

end;

ans:=n-t;if ans=0 then

begin

writeln(ans);

halt;

end;

t:=0;

for i:=1 to n do f[i]:=0;

for i:=n downto 1 do

begin

j:=find(1,t,a[i]);

if j>t then inc(t);

f[j]:=a[i];

end;

if n-t<ans then ans:=n-t;

writeln(ans);

end.

已经用了O(n log n)的算法 可无奈第十点数据实在太大 谁能给出下主意??

查看更多回复
提交回复