Hướng dẫn giải của VOI 06 Bài 7 - Dãy con dài nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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); } }
Bình luận