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

#include <iostream>
#include <algorithm>
#include <cstdio>
#define oo 1000111222
using namespace std;

int main()
{
    int test,n,k,l[40000],r[40000],a[40000];
    cin >> test;
    while (test--)
    {
        cin >> n >> k;
        for (int i=0;i<n;i++) scanf("%d",a+i);
        for (int i=n;i<(n+k-1)/k*k;i++) a[i]=oo;
        n=(n+k-1)/k*k;
        for (int i=0;i<n;i++) 
            if (i%k==0) l[i]=a[i];
            else l[i]=min(l[i-1],a[i]);
        for (int i=n-1;i>=0;i--)
            if (i%k==k-1) r[i]=a[i];
            else r[i]=min(r[i+1],a[i]);
        for (int i=0,j=i+k-1;j<n && a[j]!=oo;i++,j++)
            printf("%d ",min(r[i],l[j]));
        puts("");
    }
}

Code mẫu của happyboy99x

#include <cstdio>
#include <deque>
using namespace std;

int n, k;
int a[17005];
deque<int> dq;

void push( int x ) {
    while ( !dq.empty() && a[dq.back()] >= a[x] ) dq.pop_back();
    dq.push_back(x);
}

void pop( int x ) {
    while ( !dq.empty() && dq.front() <= x ) dq.pop_front();
}

int main() {
    int t; scanf( "%d", &t );
    while(t--) {
        scanf( "%d%d", &n, &k ); dq.clear();
        for( int i = 0; i < n; ++i ) scanf( "%d", a+i );
        for( int i = 0; i < k; ++i ) push(i);
        printf( "%d", a[dq.front()] );
        for( int i = k; i < n; ++i ) {
            pop(i-k); push(i);
            printf( " %d", a[dq.front()] );
        }
        putchar('\n');
    }
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>

using namespace std;

static struct IO {
    char tmp[1 << 10];

    // fast input routines
    char cur;

//#define nextChar() (cur = getc_unlocked(stdin))
//#define peekChar() (cur)
    inline char nextChar() { return cur = getc_unlocked(stdin); }
    inline char peekChar() { return cur; }

    inline operator bool() { return peekChar(); }
    inline static bool isBlank(char c) { return (c < '-' && c); }
    inline bool skipBlanks() { while (isBlank(nextChar())); return peekChar() != 0; }

    inline IO& operator >> (char & c) { c = nextChar(); return *this; }

    inline IO& operator >> (char * buf) {
        if (skipBlanks()) {
            if (peekChar()) {
                *(buf++) = peekChar();
                while (!isBlank(nextChar())) *(buf++) = peekChar();
            } *(buf++) = 0; } return *this; }

    inline IO& operator >> (string & s) {
        if (skipBlanks()) { s.clear(); s += peekChar();
            while (!isBlank(nextChar())) s += peekChar(); }
        return *this; }

    inline IO& operator >> (double & d) { if ((*this) >> tmp) sscanf(tmp, "%lf", &d); return *this; }

#define defineInFor(intType) \
    inline IO& operator >>(intType & n) { \
        if (skipBlanks()) { \
            int sign = +1; \
            if (peekChar() == '-') { \
                sign = -1; \
                n = nextChar() - '0'; \
            } else \
                n = peekChar() - '0'; \
            while (!isBlank(nextChar())) { \
                n += n + (n << 3) + peekChar() - 48; \
            } \
            n *= sign; \
        } \
        return *this; \
    }

defineInFor(int)
defineInFor(unsigned int)
defineInFor(long long)

    // fast output routines

//#define putChar(c) putc_unlocked((c), stdout)
    inline void putChar(char c) { putc_unlocked(c, stdout); }
    inline IO& operator << (char c) { putChar(c); return *this; }
    inline IO& operator << (const char * s) { while (*s) putChar(*s++); return *this; }

    inline IO& operator << (const string & s) { for (int i = 0; i < (int)s.size(); ++i) putChar(s[i]); return *this; }

    char * toString(double d) { sprintf(tmp, "%lf%c", d, '\0'); return tmp; }
    inline IO& operator << (double d) { return (*this) << toString(d); }


#define defineOutFor(intType) \
    inline char * toString(intType n) { \
        char * p = (tmp + 30); \
        if (n) { \
            bool isNeg = 0; \
            if (n < 0) isNeg = 1, n = -n; \
            while (n) \
                *--p = (n % 10) + '0', n /= 10; \
            if (isNeg) *--p = '-'; \
        } else *--p = '0'; \
        return p; \
    } \
    inline IO& operator << (intType n) { return (*this) << toString(n); }

defineOutFor(int)
defineOutFor(long long)

#define endl ('\n')
#define cout __io__
#define cin __io__
} __io__;

const int N = 17001;

int minL[N], minR[N];
int n, k;

int main() {
    int nTest; cin >> nTest;
    while (nTest--) {
        cin >> n >> k;
        for (int i = 0; i < n; ++i) {
            cin >> minR[i];
            minL[i] = minR[i];
            if (i > 0 && i % k) minL[i] = min(minL[i], minL[i - 1]);
        }
        for (int i = n - 2; i >= 0; --i) if (i % k != k - 1)
            minR[i] = min(minR[i], minR[i + 1]);
        for (int i = 0; i + k <= n; ++i)
            cout << min(minR[i], minL[i + k - 1]) << ' ';
        cout << '\n';
    }
    return 0;
}

Code mẫu của RR

uses math;
var
  a,l,r:array[1..50111] of longint;
  nn,test,i,n,k:longint;
begin
  read(test);
  for test:=1 to test do
    begin
      read(n,k); nn:=n;
      for i:=1 to n do
        read(a[i]);

      while (n mod k<>0) do
        begin
          inc(n);
          a[n]:=maxlongint;
        end;

      for i:=1 to n do
        if i mod k=1 then l[i]:=a[i]
        else l[i]:=min(l[i-1],a[i]);

      for i:=n downto 1 do
        if i mod k=0 then r[i]:=a[i]
        else r[i]:=min(r[i+1],a[i]);

      for i:=1 to nn-k+1 do
        write(min(r[i],l[i+k-1]),' ');
      writeln;
    end;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long T,n,k,a[17001],left[17001],right[17001],r[17002],l[17002],f[17001];
scanf("%ld",&T);
for(long i=1;i<=T;i++)
  {
  scanf("%ld %ld",&n,&k);
  for(long j=1;j<=n;j++)
    scanf("%ld",&a[j]);
  long u=1;
  r[1]=1;
  while(r[u]!=n+1)
    {
    long t=r[u]+1;
    if(a[t]<a[r[u]])
      {
      for(long j=u;j>=1;j--)
        {
        if(a[t]<a[r[j]])
          {
          right[r[j]]=t-1;
          u--;
          }
        else  
          break;
        }
      u++;
      r[u]=t;  
      }
    else if(t==n)
      {
      for(long j=u;j>=1;j--)
        right[r[j]]=n;          
      break;
      }
    else
      {
      u++;
      r[u]=t;
      }
    }            
  right[n]=n;
  u=1;
  l[1]=n;
  //printf("%ld %ld %ld %ld",right[4],right[3],right[2],right[1]);
  while(l[u]!=0)
    {
    long t=l[u]-1;
    if(a[t]<a[l[u]])
      {
      for(long j=u;j>=1;j--)
        {
        if(a[t]<a[l[j]])
          {
          left[l[j]]=t+1;
          u--;
          }
        else  
          break;
        }
      u++;
      l[u]=t;  
      }
    else if(t==n)
      {
      for(long j=u;j>=1;j--)
        left[l[j]]=n;          
      break;
      }
    else
      {
      u++;
      l[u]=t;
      }
    }
  left[1]=1;  
  //printf("%ld %ld %ld",left[4],left[3],left[2]);              
  for(long j=1;j<=n;j++)
    {
    if(left[j]<j-k+1)
      left[j]=j-k+1;
    if(right[j]>j+k-1)
      right[j]=j+k-1;
    for(long t=left[j];t<=right[j]-k+1;t++)
      f[t]=a[j];
    }
  for(long j=1;j<=n-k+1;j++)
    printf("%ld ",f[j]);
  printf("\n");
  }
//getch();
}

Code mẫu của ll931110

Program MINK;
        Const
                input  = '';
                output = '';
                  maxn = 20000;
        Var
                a,stack: array[0..maxn] of longint;
                n,t,k,i: longint;
             front,rear: longint;
                  fi,fo: text;

Procedure init;
          Var
                i: integer;
          Begin
                Readln(fi, n, k);
                For i:= 1 to n do read(fi, a[i]);

                a[0]:= -1;
          End;

Procedure solve;
          Var
                front,rear,i: integer;
          Begin
                front:= 1;      rear:= 1;
                stack[0]:= 0;   stack[1]:= 1;

                For i:= 2 to k - 1 do
                        Begin
                                While (a[i] <= a[stack[rear]]) and (rear >= front) do dec(rear);

                                inc(rear);
                                stack[rear]:= i;
                        End;

                For i:= k to n do
                        Begin
                                If stack[front] + k <= i then inc(front);
                                While (a[i] <= a[stack[rear]]) and (rear >= front) do dec(rear);

                                inc(rear);
                                stack[rear]:= i;

                                Write(fo, a[stack[front]], ' ');
                        End;

                Writeln(fo);
          End;

Begin
        Assign(fi, input);
                Reset(fi);

        Assign(fo, output);
                Rewrite(fo);

        Readln(fi, t);
        For i:= 1 to t do
                Begin
                        init;
                        solve;
                End;

        Close(fo);
        Close(fi);
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   17171
int p[MAX];
int a[MAX];
int f[MAX][20];
int n,k;
int t,c;
int min(int x,int y) {
    if (x<y) return (x); else return (y);
}
void finit(void) {
    int i;
    p[0]=1;
    i=0;
    while (p[i]<MAX){
        i=i+1;
        p[i]=p[i-1]*2;
    }
}
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    int i,j;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&a[i]);
        f[i][0]=a[i];
    }
    for (j=1;p[j]<=n;j=j+1)
        for (i=1;i+p[j]-1<=n;i=i+1)
            f[i][j]=min(f[i][j-1],f[i+p[j-1]][j-1]);
}
int mina(int u,int v) {
    if (u==v) return (a[u]);
    int k=0;
    while (p[k]<=v-u+1) k=k+1;
    k=k-1;
    return (min(f[u][k],f[v-p[k]+1][k]));
}
void process(void) {
    int i;
    for (i=1;i<n-k+1;i=i+1) printf("%d ",mina(i,i+k-1));
    printf("%d\n",mina(n-k+1,n));
}
int main(void) {
    finit();
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) {
        init();
        process();
    }
}

Code mẫu của khuc_tuan

Const   fi      =   '';
        fo      =   '';
        maxn    =   20000;
Var     f,f2    :   text;
        a,r,l,s :   array[0..maxn]of longint;
        n,k     :   longint;
Procedure openf;
   begin
     assign(f,fi); reset(f);
     assign(f2,fo); rewrite(f2);
   end;
Procedure closef;
   begin
     close(f); close(f2);
   end;
Procedure inp;
   var i:longint;
   begin
     readln(f,n,k);
     for i:=1 to n do read(f,a[i]);
     fillchar(l,sizeof(l),0);
     fillchar(r,sizeof(r),0);
     readln(f);
   end;
Procedure solve;
   var i,j,last:longint;
   begin
     fillchar(s,sizeof(s),0); last:=0;
     a[0]:=maxlongint; a[n+1]:=maxlongint;
     for i:=1 to n do
       begin
         while (last>0) and (a[i]<=a[s[last]]) do dec(last);
         l[i]:=s[last]+1;
         inc(last); s[last]:=i;
       end;
     fillchar(s,sizeof(s),0); last:=0; s[0]:=n+1;
     for i:=n downto 1 do
       begin
         while (last>0) and (a[i]<=a[s[last]]) do dec(last);
         r[i]:=s[last]-1;
         inc(last); s[last]:=i;
       end;
   end;
Procedure Out;
   var i,j:longint;
   begin
     j:=1;
     for i:=1 to n-k+1 do
       begin
         while not ((l[j]<=i) and (r[j]>=i+k-1) and (j>=i)) do inc(j);
         write(f2,a[j],' ');
       end;
     writeln(f2);
   end;
Procedure process;
   var i,t:longint;
   begin
     readln(f,t);
     for i:=1 to t do
       begin
         inp;
         solve;
         Out;
       end;
   end;
Begin
  openf;
  process;
  closef;
End.