[POI2009]ARC-Architects

题意：

给定一个序列，从中挑选k个数，满足下标单调递增，并且字典序最小；

思路：

由于字典序最小，所以考虑贪心，即前面的数尽可能大，所以用单调队列维护最大值；

细节：

注意单调队列对头应该是上次选的数的下一个数，另外要满足k个数，所一直以维护队尾；

因为是交互题，注意变量名重复；

代码

/*************************************************************************}

{*                                                                       *}

{*                     XVI Olimpiada Informatyczna                       *}

{*                                                                       *}

{*   Zadanie: Architekci (ARC)                                           *}

{*   Plik:    carclib.c                                                  *}

{*   Autor:   Bartosz Gorski                                             *}

{*   Opis:    Biblioteka do wczytywania danych wejsciowych i wypisywania *}

{*            wyniku                                                     *}

{*                                                                       *}

{*************************************************************************/

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

#define MAGIC_BEGIN -435634223

#define MAGIC_END -324556462

#define MIN_K 1

#define MAX_K 1000000

#define MAX_N 15000000

#define MIN_A 1

#define MAX_A 1000000000

#define MIN_TYP 1

#define MAX_TYP 3

#define MIN_PAR 0

#define MAX_PAR 1000000000

#define ERROR 0

#define CORRECT 1

#define unlikely(x) __builtin_expect(!!(x), 0)

static int init = 0; // czy zostala juz wywolana funkcja inicjuj()

static int lib_n; // ile biblioteka podala juz liczb

static int con_k; // ile zawodnik podal liczb

static int N, K, A, TYP, PAR; // parametry testu wczytywane z pliku

static int bre, len_sub, bou, is_end; // zmienne pomocnicze

static int rand2_status = 198402041;

static inline int rand2(int a, int b){

  rand2_status = rand2_status * 1103515245 + 12345;

  int x = rand2_status;

  if (x < 0) x = -x; // -2^31 sie nie zdarza :D

  x >>= 1;

  x = a + x % (b - a + 1);

  return x;

}

/* test losowy */

static inline int random_test()

{

    return rand2(1, A);

}

/* test z dlugim podciagiem nierosnacym */

static inline int decreasing_test()

{

    int tmp;

    if(bre == 0) {

        bre = rand2(0, (N - lib_n + 1 - len_sub));

        tmp = A;

        A -= rand2(0, (A - 1) / len_sub);

        len_sub--;

    }

    else {

        bre--;

        tmp = rand2(1, A);

    }

    return tmp;

}

/* test z dlugim podciagiem niemalejacym */

static inline int increasing_test()

{

    return bou - decreasing_test();

}

static void finish(int res, char *com)

{

    if(res == ERROR)

        printf("%s\n", com);

    exit(0);

}

/* Inicjuje dane wejsciowe i zwraca liczbe projektow */

int inicjuj()

{

    if(init == 1)

        finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!");

    init = 1;

    scanf("%d", &K);

    if (K > 0){

      TYP = 0;

      N = MAX_N + 2;

      return K;

    }

    int magic_begin, magic_end;

    scanf("%d%d", &magic_begin, &TYP);

    if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP)

        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");

    scanf("%d%d%d%d", &N, &K, &A, &PAR);

    if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A

        || PAR < MIN_PAR || PAR > MAX_PAR)

        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");

    scanf("%d", &magic_end);

    if(magic_end != MAGIC_END)

        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");

    con_k = 0;

    lib_n = 0;

    is_end = 0;

    if(TYP == 2 || TYP == 3) {

        len_sub = PAR;

        bre = 0;

    }

    if(TYP == 2)

        bou = A--;

    return K;

}

/* Sluzy do wczytania ciagu reprezentujacego jakosci projektow */

int wczytaj()

{

    if(unlikely(init == 0))

        finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");

    if(unlikely(lib_n > N || is_end == 1))

        finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!");

    if(unlikely(lib_n == N))

        return 0;

    lib_n++;

    switch (TYP) {

      case 0:

        scanf("%d", &A);

        if(A == 0)

          is_end = 1;

        return A;

        break;

      case 1: return random_test(); break;

      case 2: return increasing_test(); break;

      case 3: return decreasing_test(); break;

      default:

              finish(ERROR, "Nieznany typ testu");

    }

    return -1;

}

/* Sluzy do wypisania wyznaczonego podciagu */

void wypisz(int jakoscProjektu)

{

    if(init == 0)

        finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");

    printf("%d\n", jakoscProjektu);

    if(++con_k == K)

        finish(CORRECT, "");

}

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN=2e7+7;

int n,k,h1=1,h2=0,t=1;

int a[MAXN],q[MAXN];

int main(){

    k=inicjuj();

    while(1) {

        a[++n]=wczytaj();

        if(a[n]==0)break;

    }

    n--;

//    cout<<n<<" "<<k<<" "<<h1<<" "<<h2<<" "<<t<<" "<<q[1]<<"\n";

    for(int i=1;i<=k;i++){

        while(t<=n-k+i){

            while(h2>=h1&&q[h2]<a[t]){

                h2--;

            }

            q[++h2]=a[t];

            t++;

        }

//        cout<<q[h1]<<"\n";

        int jakoscProjektu=q[h1];

        wypisz(jakoscProjektu);

//        wypisz('\n');

        h1++;

    }

}