Đề bài:
Thuật toán:
- Sừ dụng thuật toán tìm max/min trên một đoạn tịnh tiến.
Code:
uses math; const fi=''; fo=''; maxn=trunc(1e6)+3; var st : array[1..maxn] of longint; a,l,r : array[1..maxn] of longint; i,j,n : longint; res : int64; top : longint; procedure enter; begin assign(input,fi);reset(input); readln(n); for i:=1 to n do read(a[i]); end; procedure push(x : longint); begin inc(top); st[top] := x; end; function get: longint; begin get := st[top]; end; procedure process; begin top :=0 ; for i:=1 to n do begin while (top<>0) and (a[get]>=a[i]) do dec(top); if top=0 then l[i] := 0 else l[i] := get; push(i); end; top := 0; for i:=n downto 1 do begin while (top<>0) and (a[get]>=a[i]) do dec(top); if top=0 then r[i]:=n+1 else r[i] := get; push(i); end; for i:=1 to n do if r[i]-l[i]-1>=a[i] then res := max(res, a[i]); end; procedure print; begin assign(output,fo);rewrite(output); writeln(res); end; begin enter; process; print; end. |
Speak Your Mind