QBDIVSEQ - Chia dãy

Tác giả: ladpro98

Ngôn ngữ: Pascal

program qbdivseq;
uses    math;
const   fi='';
        maxN=100005;
var     a,f:array[1..maxN] of longint;
        n,d:longint;

procedure input;
var     f:text;
        i:longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n);
        for i:=1 to n do
        readLN(f,a[i]);
        close(f);
end;

function find(r,key:longint):longint;
var     l,m,k:longint;
begin
        l:=1;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if f[m]<=key then
                begin
                        k:=m;
                        r:=m-1;
                end
                else
                l:=m+1;
        end;
        exit(k);
end;

procedure process;
var     i:longint;
begin
        d:=1;
        for i:=1 to n do
        if a[i]<f[d] then
        begin
                inc(d);
                f[d]:=a[i];
        end
        else
        f[find(d,a[i])]:=a[i];

end;

begin
        input;
        process;
        write(d);
end.

Download