nlogn的最长不下降子序列【tyvj1254挑选士兵】

 1 var
 2   a,d:Array[-1..300000]of longint;
 3   i,n,m,k,l:longint;
 4 function erfen(x:longint):longint;
 5   var mid,h,t:longint;
 6   begin
 7   h:=1;t:=l;
 8   erfen:=0;
 9   while h<=t do
10     begin
11     mid:=(h+t)shr 1;
12     if d[mid]<=x then
13       begin erfen:=mid;h:=mid+1;end
14     else
15       t:=mid-1;
16     end;
17   end;
18 
19 begin
20   readln(n);
21   for i:=1 to n do
22     read(a[i]);
23   d[0]:=-maxlongint; l:=0;
24   for i:=1 to n do
25     if a[i]>=d[l] then
26       begin
27       inc(l);
28       d[l]:=a[i];
29       end
30     else
31       begin
32       k:=erfen(a[i]);
33       if a[i]<d[k+1] then d[k+1]:=a[i];
34       end;
35   writeln(l);
36   end.

View Code

------------------------------------------------------------------------- 花有重开日，人无再少年