Part 1：关于贪心与数据结构

一个贪心算法的本质是：不断做出当前情况的最优解，最终可以得到全局最优解

只要这个问题的阶段决策满足上述要求，就可以使用贪心法求解

所以，我们要使得当前阶段决策最优，通常会用到“最值”，即可做出的选择中，最好的那一个

于是，数据结构应运而生，它可以很好的帮助我们维护一堆数据的某个性质，从而有效提高程序的运行效率

（这才是数据结构诞生的意义，所以暴力数据结构题都是毒瘤）

常用于优化其他算法的数据结构：单调队列、单调栈、优先队列、树状数组（线段树）等等

Part 2：例题整理

洛谷P3487[POI2009]ARC-Architects

标签与传送门

传送门：洛谷P3487[POI2009]ARC-Architects

标签：单调队列优化贪心

题意梳理

一句话来说：在整个长度为\(n\)的序列中选出长度为\(k\)的子序列，使得这\(k\)个数构成的序列的字典序最大

\(Solution\)

考虑如何最大化字典序，分析字典序的性质——越靠前的数越大，那么这个字典序就越大

比如两个序列：\(a=[2,3000,1000],b=[3,1,1]\)，虽然\(a\)的第二、三项很大，但是因为第一项\(2<3\)，所以排列\(a\)的字典序小于排列\(b\)的字典序

那么贪心的想：只要从第一个依次向后选，并且每次保证进来的数最大，这样贪心的选\(k\)次，就可以保证字典序最大

本题数据较大，\(n\leq 1.5\times 10^7\)，需要使用\(O(n)\)的算法维护最大值，想到单调队列维护

有了大体思路框架之后，开始处理实现细节问题：

1. 使用单调队列维护\(n-k+1\)个数中的最大值，这样可以保障我们能够选出\(k\)个数

2. 先把前\(n-k\)个数入队，然后每入队一个元素，统计一次答案，时间复杂度\(O(n)\)

3. 题目中要求每个数最多选\(1\)次，所以在维护单调队列时，每记录一次最大值当作答案，队头就要弹出

4. 原题是一道交互题，需要下载一个交互库，使用前注意变量名不要和交互库中的变量名重复（交互库会和AC代码一起给出）

\(Code\)

/*************************************************************************}
{*                                                                       *}
{*                     XVI Olimpiada Informatyczna                       *}
{*                                                                       *}
{*   Zadanie: Architekci (ARC)                                           *}
{*   Plik:    carclib.c                                                  *}
{*   Autor:   Bartosz Gorski                                             *}
{*   Opis:    Biblioteka do wczytywania danych wejsciowych i wypisywania *}
{*            wyniku                                                     *}
{*                                                                       *}
{*************************************************************************/

#include 
#include 
#include 

#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, "");
}
//以上均是交互库内容
#define maxn 15000010
#define inf 0x3f3f3f3f

struct Queue{
	int und,num;//建立结构体，存储下标和数字大小
}q[maxn];//声明单调队列q

int main(){
	int a[maxn],n,k;
	int ans[maxn],it;
	k=inicjuj();
	for(int i=1;;i++){
		a[i]=wczytaj();//按要求读入
		if(a[i]==0) break;
		n++;//n是元素个数 
	}
	k=n-k+1;
	int i,head=1,tial=0;//建立单调队列维护k个数中最大值 
	for(i=1;i

#include
#include
#include
#include
#include
#include
#include

3
100 0 0 
100 50 50

#include
#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
#include
#include
#include