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.

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

Please read the guidelines before commenting.


There are no comments at the moment.