关于单调队列

· · 个人记录

虽然单调队列不常考，都是经常和动态规划放一起，就让我们来了解一下。

所谓单调是指单调性，要么递增，要么递减。

这是个从队头到队尾的单调递增队列。

（ps:本文的队头用hh表示，队尾用tt表示，队头在左，队尾在右）

让我们看一下单调队列的实现。

  for(int i=1;i<=n;i++)
  {
      while(hh<=tt && a[q[tt]]>=a[i])//单调递增队列 
          tt--;
      q[++tt]=i;
  }

  for(int i=1;i<=n;i++)
  {
      while(hh<=tt && a[q[tt]]<=a[i])//单调递减队列 
          tt--;
      q[++tt]=i;
  }

题目描述

一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0。

输入格式

第一行两个整数，分别表示 n，m。

第二行，n 个正整数，为所给定的数列 a_i。

输出格式

n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_i

之前 m 个数的最小值。

解法

对于这种求最小值的，我们一般采用单调递增队列（个人经验）。

我们不妨举个例子：

有这么几个数：1 2 4 3，那么此时 n为4，m为3。

先进行进队操作，首先1进队列，2比1大，也进来，4比2大，也进来，那么1最小，就输出队头1（最大最小分开考虑）。

随后，我们发现，3比4大，破坏了单调性。

于是就要出队，4出去，3进来，4再进来，那么此时的队列就符合我们的要求。

调换位置后，窗口滑动，现在在窗口里的数为1 2 3，那么还是输出1。

思路出来以后，就来看看代码。

  #include<iostream>
  #include<cstdio>
  using namespace std;
  const int N=2e6+200;
  int n,m,a[N];
  int q[N],hh,tt=-1;
  int main()
  {
      scanf("%d %d",&n,&m);
      for(int i=1;i<=n;i++)
          scanf("%d",&a[i]);
      for(int i=1;i<=n;i++)
      {
          if(hh<=tt && i-q[hh]>m)//如果队列不空，判断队头的下标是否超出范围
              hh++;
          printf("%d\n",a[q[hh]]);
          while(hh<=tt && a[q[tt]]>=a[i])//单调递增队列 
              tt--;
          q[++tt]=i;
      }
      return 0;
  }

基本思路同上，不再熬述。

习题1：P2032 扫描

习题2：P1886 滑动窗口 /【模板】单调队列

例题：P1090 合并果子 / [USACO06NOV] Fence Repair G

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。

输入格式

共两行。 第一行是一个整数 n(1\leq n\leq 10000)n(1≤n≤10000) ，表示果子的种类数。 第二行包含 n 个整数，用空格分隔，第 i 个整数 a_i(1\leq a_i\leq 20000) 是第 i 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^{31}。

解法

对于这道题，我们很容易地想到，要使体力值最小，我们每次合并都得选最小的两个。

于是我们就会想到用 sort 排序。

时间复杂度就是 n\,(n\,log\,n) ，但是 n 最大为 10000 ，明显会超时。

所以要用二叉堆来排序。

由于优先队列默认是大根堆，只能取最大值，所以我这里还涉及到重载运算符（让原来大的变“小”，小的变“大”）。

重载运算符的实现：

    #include<queue>
  struct node{
      int t;
  };
  bool operator <(const node &x,const node &y)
  {
      return x.t>y.t;
    /*重载小于号 ,优先队列默认是大根堆，只能取到最大值，
    现在想取到最小值，所以需要把优先队列改为小根堆，需要重载小于号*/
  }

那么实现小根堆以后，就可以用单调递增队列来做这道题


  #include<iostream> 
  #include<cstdio>
  #include<vector>
  #include<queue>
  using namespace std;
  struct node{
      int t;
  };
  priority_queue <node> q;
  bool operator <(const node &x,const node &y)
  {
      return x.t>y.t;
  /*重载小于号 ,优先队列默认是大根堆，只能取到最大值，
  现在想取到最小值，所以需要把优先队列改为小根堆，需要重载小于号*/
  }
  node a[10100];
  int main()
  {
      int n,ans=0;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
      {
          scanf("%d",&a[i].t);
          q.push(a[i]);
      }
      if(n==1)//特殊情况
      {
          printf("%d",a[1].t);
          return 0;
      }
      while(true)//合并果子ing 
      {
          node x,y;
          x=q.top();
          q.pop();
          y=q.top();
          q.pop();
          ans=ans+x.t+y.t;//统计体力值 
          if(q.empty())//如果队列为空
          {
              break;//合并完了，走人 
          } 
          else
          {
              node z;
              z.t=x.t+y.t;
              q.push(z);//得到这次合并果子的体力值 
          }
      }
      printf("%d",ans);
      return 0;
    }

习题：P2168 [NOI2015]荷马史诗

例题：298.围栏

题目描述

有 N 块木板从左到右排成一行，有 M 个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。

第 i 个木匠要么不粉刷，要么粉刷包含木板 S_i 的，长度不超过 L_i 的连续的一段木板，每粉刷一块可以得到 P_i 的报酬。

不同工匠的S_i不同。

请问如何安排能使工匠们获得的总报酬最多。

输入格式

第一行包含两个整数 N 和 M 。

接下来M行，每行包含三个整数 L_i , P_i , S_i 。

输出格式

输出一个整数，表示结果。

数据范围

$1≤M≤100$ , $1≤Pi≤10000$ . ### 解法 这道题是单调队列优化DP。 ### 首先我们定义一个状态：$f\,[\,i\,]\,[\,j\,]$ 。 $f\,[\,i\,][\,j\,]$表示前 $i$ 个工匠粉刷前 $j$ 块木板，工匠们能获得的最多报酬。 分情况考虑： 1. 情况1： 第 i 个工匠不刷，此时，$f\,[\,i\,]\,[\,j\,]\,=\,f\,[\,i-1\,]\,[\,j\,]$ 。 2. 情况2： 第 j 块木板可以不刷，此时，$f\,[\,i\,]\,[\,j\,]\,=\,f\,[\,i\,]\,[\,j-1\,]$ 。 * 情况3： 第 $i$ 个工匠刷第 $k+1$ 块到第 $j$ 块木板。但是，该工匠粉刷总数不能超过 $L_i$ ，且必须粉刷到第 $S_i$ 块，所以需要满足：$k+1\,≤\,S_i\,≤\,j$ 并且 $j-k≤L_i$ 。 ### 状态转移方程： $f\,[\,i\,]\,[\,j\,]\,=\,max\,(\,f\,[\,i-1\,]\,[\,k\,]\,+\,P_i\,\times\,(\,j\,-\,k\,)\,)$ 。 其中 $j-Li\,≤\,k\,≤\,Si-1$ , $j≥Si$ 。（可根据情况3推出） 我们在考虑内层循环 $j$ 以及决策 $k$ 时，可以把外层循环变量 $i$ 看作定值，这样，状态转移方程中的各项可分为两部分： 1. $P_i\,\times\,j$ 。 除定值 $i$ 外，只有状态变量 $j$ 。 2. $f[\,i-1\,]\,[\,k\,]\,-\,P_i\,\times\,k$ 。 除定值 $i$ 外，只有决策变量 $k$ 。 那么，状态转移方程可以改写为： $f[\,i\,]\,[\,j\,]\,=\,P_i\,\times\,j\,+\,max\,(\,f\,[i\,-\,1\,]\,[\,k\,]\,-\,P_i\,\times\,k\,)$ 。 其中 $j-L_i\,≤k\,≤\,S_i-1$ ，$j\,≥\,S_i$ 。 当 $j$ 变大时，$k$ 的取值范围上界 $S_i -1$ 不变，下界 $j-L_i$ 变大， 我们比较任意两个决策 $k_1$ 和 $k_2$ ，不妨设 $k_1 ,<\,k_2\,≤\,S_i-1$ ,因为 k_2 在 k_1 的后面，所以随着 $j$ 的增加，$k_1$ 会比 $k_2$ 更早从范围 $j-L_i$ ~ $S_i-1$中 被排除。如果还满足 : $f\,[\,i-1\,]\,[\,k_1\,]\,-\,Pi\,\times\,k_1\,≤\,f\,[\,i-1\,]\,[\,k_2\,]\,-\,P_i\,\times\,k_2$ 。 那么就说明$k-2$ 不但比 $k-1$ 更优，还留下时间比 $k_1$ 更长，这样的话，$k_1$ 就是无用的，应该直接排除。所以，我们可以维护一个决策点 $k$ 单调递增，数值 $f\,[\,i-1\,]\,[\,k\,]\,-\,P_i\,\times\,k$ 单调递减的队列，只有这个队列中的决策才有可能在某一时刻成为最优决策。这个单调队列支持以下操作： 1. 当 $j$ 变大时，检查队头元素，把小于 $j-L_i$ 的决策出队。 2. 需要查询最优决策时，队头就是要求的。 3. 有一个新的决策要加入候选集合时，在队尾检查 $f\,[\,i-1\,]\,[\,k\,]\,-\,P_i\,\times\,k$ 的单调性，把无用决策从队尾直接出队，最后把新决策加入队列 程序中，当内层循环开始时 $(j=Si)$，建立一个空的单调队列，把 $max(S_i-L_i,0),S_i-1$ 中的决策一次加入候选集合，对于每个 $j=S_i$ ~ $N$，先在队头检查合法性，然后取队头为最优决策进行状态转移。 代码如下： ``` #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; const int N=16500,M=150; struct node{ int L,P,S; }; node a[M]; int n,m,f[M][N]; int q[N],hh,tt=-1; bool cmp(const node &x,const node &y) { return x.S<y.S; } int jisuan(int i,int k) { return f[i-1][k]-a[i].P*k; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) scanf("%d %d %d",&a[i].L,&a[i].P,&a[i].S); sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++) { //单调队列初始化 hh=0,tt=-1; //候选集合进队 for(int k=max(0,a[i].S-a[i].L);k<=a[i].S-1;k++) { //决策入队，维护队尾单调性，从队头到队尾单调递减 while(hh<=tt && jisuan(i,q[tt])<=jisuan(i,k)) tt--; q[++tt]=k; } for(int j=1;j<=n;j++) { f[i][j]=max(f[i-1][j],f[i][j-1]); //粉刷第 k+1~j块模木板时的转移 if(j>=a[i].S) { //排除队头不合法的决策 while(hh<=tt && q[hh]<j-a[i].L) hh++; //队列非空时，取队头进行状态转移 if(hh<=tt) f[i][j]=max(f[i][j],jisuan(i,q[hh])+a[i].P*j); } } } printf("%d",f[m][n]); return 0; } ``` 习题：[332. 股票交易](https://www.acwing.com/problem/content/334/) 感谢一些大佬为我指出错误。