MINK – spoj

Đề bài:

• http://vn.spoj.com/problems/MINK/

Thuật toán:

• Bài này chỉ thuần sử dụng thuật toán Kỹ thuật sử dụng Deque tìm Max/Min trên một đoạn tịnh tiến

Code:

• C++ (xem)
• Pascal (xem)

const   fi='';
        fo='';
        maxn=17000;
var     a:array[1..maxn] of longint;
        hold:array[1..maxn] of integer;
        i,j,n,k,t:integer;
        top,below:integer;
procedure push(i:integer);
begin
    while (top<>below-1) and (a[i]top+1) and (hold[below]<=i) do inc(below);
end;
procedure print;
begin
    write(a[hold[below]],' ');
end;
procedure solve;
var     i:integer;
begin
    top:=0; below:=1;
    for i:=1 to k do push(i); print;
    for i:=k+1 to n do
        begin
            pop(i-k);
            push(i);
            print;
        end;
    writeln;
end;
procedure main;
var     i,j:integer;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);

    readln(t);
    for i:=1 to t do
        begin
            read(n,k);
            for j:=1 to n do read(a[j]);
            solve;
        end;

    close(input);close(output);
end;
begin
    main;
end.

#include 
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector VI;
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
deque q;
int i, n, k, a[20000], t, tt;
int main() {
	cin >> t;
	for (int tt=1; tt<=t; tt++) {
        cin >> n >> k;
        for (int i=1; i<=n; i++) cin >> a[i];
        while (!q.empty()) q.pop_back();
        for (int i=1; i<=n; i++) {
            while ((!q.empty())&&(q.front() < i-k+1)) q.pop_front();
            while ((!q.empty())&&(a[q.back()]>a[i])) q.pop_back();
            q.push_back(i);
            if (i>=k) cout << a[q.front()] << " ";
        }
        cout << endl;
	}
	return 0;
}