Editorial for VOI 06 Bài 7 - Dãy con dài nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=50005; var n,re,p,num:longint; a,d,max,b,e:array[0..maxn] of longint; procedure rf; var i,t:longint; begin assign(input,fi); reset(input); read(n,p); a[0]:=0; d[0]:=0; for i:=1 to n do begin read(t); a[i]:=a[i-1]+t; d[i]:=i; end; close(input); end; procedure sort(l,r:longint); var x,y,i,j,u:longint; begin i:=l; j:=r; x:=a[(i+j) shr 1]; u:=d[(i+j) shr 1]; repeat while (a[i]<x) or ((a[i]=x) and (d[i]>u)) do i:=i+1; while (a[j]>x) or ((a[j]=x) and (d[j]<u)) do j:=j-1; if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=d[i]; d[i]:=d[j]; d[j]:=y; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure edit; var i:longint; begin num:=0; b[0]:=a[0]; e[0]:=d[0]; for i:=1 to n do if a[i]<>b[num] then begin inc(num); b[num]:=a[i]; e[num]:=d[i]; end; max[num]:=e[num]; for i:=num-1 downto 0 do if e[i]>max[i+1] then max[i]:=e[i] else max[i]:=max[i+1]; end; function bs(x:longint):longint; var l,r,m,j:longint; begin l:=0; r:=num; while l<=r do begin m:=(l+r) shr 1; if b[m]=x then break; if b[m]<x then l:=m+1 else r:=m-1; end; for j:=m-1 to m+1 do if (j>=0) and (j<=num) and (b[j]>=x) then break; bs:=j; end; procedure pr; var i,t:longint; begin sort(0,n); edit; re:=-1; for i:=0 to n do begin if a[i]+p>a[n] then break; if a[i]+p<a[0] then t:=0 else if (i=0) or (a[i]<>a[i-1]) then t:=bs(a[i]+p); if max[t]-d[i]>re then re:=max[t]-d[i]; end; end; procedure wf; begin assign(output,fo); rewrite(output); writeln(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
Code mẫu của ladpro98
program nkmaxseq; uses math; const fi=''; maxN=50005; var a,s,mins:array[0..maxN] of longint; n,res,p:longint; procedure input; var f:text; i:longint; begin assign(f,fi); reset(f); readln(f,n,p); for i:=1 to n do readln(f,a[i]); close(f); end; procedure init; var i,m:longint; begin minS[0]:=0; s[1]:=a[1]; for i:=2 to n do s[i]:=s[i-1]+a[i]; m:=s[1]; for i:=1 to n do mins[i]:=min(mins[i-1],s[i]); end; function find(r,key:longint):longint; var l,m,k:longint; begin l:=0; k:=n+1; while l<=r do begin m:=(l+r) shr 1; if mins[m]<=key then begin k:=m; r:=m-1;; end else l:=m+1; end; exit(k); end; procedure process; var i,pos:longint; begin for i:=2 to n do begin pos:=find(i,s[i]-p); if pos<>n+1 then res:=max(res,i-pos); end; end; begin input; init; process; if res=0 then res:=-1; write(res); end.
Code mẫu của RR
uses math; const MAXN=50111; var i,n,p:longint; a,sum,ind:array[0..MAXN] of longint; procedure swap(var a,b:longint); var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure sort(l,r:longint); var i,j,ms,mi,key:longint; begin i:=l; j:=r; key:=l+random(r-l+1); ms:=sum[key]; mi:=ind[key]; repeat while (sum[i]<ms) or ((sum[i]=ms) and (ind[i]<mi)) do inc(i); while (sum[j]>ms) or ((sum[j]=ms) and (ind[j]>mi)) do dec(j); if i<=j then begin swap(sum[i],sum[j]); swap(ind[i],ind[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure solve; var i,j,nn,res:longint; begin j:=0; nn:=n+1; res:=0; for i:=1 to n do begin while sum[j+1]<=sum[i]-p do begin inc(j); nn:=min(nn,ind[j]); end; if nn<=ind[i] then res:=max(res,ind[i]-nn); end; if res=0 then res:=-1; writeln(res); end; begin read(n,p); for i:=1 to n do begin read(a[i]); sum[i]:=sum[i-1]+a[i]; ind[i]:=i; end; inc(n); ind[n]:=0; sum[n]:=0; sort(1,n); solve; end.
Code mẫu của hieult
#include <cstdio> //#include <conio.h> #include <algorithm> int main() { // freopen("NKMAXSEQ.in","r",stdin); int n,p,u[50001],Id[50001],x; scanf("%d %d",&n,&p); int min=0,imin=0; u[0]=0; for(int i = 1;i<=n;i++) { scanf("%d",&x); u[i] = u[i-1]+x; if(u[i]<min) { min = u[i]; imin = i; } Id[i] = imin; } int i = Id[n],j=n,t=0; while(true) { while(i<j && j-i>t && u[j]-u[i]<p) j--; if(j-i>t) t = j-i; if(i==0) break; i = Id[i-1]; } if(t==0) printf("-1"); else printf("%d",t); // getch(); }
Code mẫu của ll931110
program nkmaxseq; const input = ''; output = ''; maxn = 50000; maxv = 1000000001; var a,s: array[0..maxn] of longint; t: array[0..6 * maxn] of longint; n,p,tmp,res: longint; procedure init; var f: text; i: longint; begin assign(f, input); reset(f); readln(f, n, p); s[0] := 0; for i := 1 to n do begin read(f, a[i]); s[i] := s[i - 1] + a[i]; end; close(f); end; procedure update(i,low,high,x: longint); var mid: longint; begin if low = high then begin t[i] := s[x]; exit; end; mid := (low + high) div 2; if x <= mid then update(2 * i,low,mid,x) else update(2 * i + 1,mid + 1,high,x); if t[2 * i] > t[2 * i + 1] then t[i] := t[2 * i + 1] else t[i] := t[2 * i]; end; procedure find(i,low,high,x: longint); var mid: longint; begin if t[i] > x then exit; if low = high then begin tmp := low; exit; end; mid := (low + high) div 2; if t[2 * i] <= x then find(2 * i,low,mid,x) else find(2 * i + 1,mid + 1,high,x); end; procedure solve; var i: longint; begin for i := 0 to 4 * maxn do t[i] := maxv; update(1,0,n,0); for i := 1 to n do begin tmp := -1; find(1,0,n,s[i] - p); if (tmp <> -1) and (res < i - tmp) then res := i - tmp; update(1,0,n,i); end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); if res = 0 then writeln(f, -1) else writeln(f, res); close(f); end; begin init; solve; printresult; end.
Code mẫu của skyvn97
Code mẫu của khuc_tuan
import java.util.*; import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.*; import com.sun.corba.se.spi.orbutil.fsm.Input; public class Main { public static void main(String[] args) throws Exception { BufferedReader kb = new BufferedReader( new InputStreamReader(System.in)); Scanner sc = new Scanner(kb.readLine()); int n = sc.nextInt(); int P = sc.nextInt(); int[] imin = new int[n+1]; int[] a = new int[n+1]; for(int i=1;i<=n;++i) a[i] = a[i-1] + Integer.parseInt(kb.readLine()); imin[0] = 0; for(int i=1;i<=n;++i) if(a[i]<a[imin[i-1]]) imin[i] = i; else imin[i] = imin[i-1]; int rj = n; int result = -1; for(int i=n-1;i>=0;--i) if(imin[i]==i) { int j; for(j=rj;j>i;--j) if(a[j]-a[i]>=P) { result = Math.max( result, j-i); break; } rj = j; } System.out.println(result); } }
Comments