什么叫单调？
• 一些数据从小到大排列 —— 单调递增
• 从大到小排列 —— 单调递减

单调队列
• 单调递增的队列：在队列的基础上，时刻保持队列中的元素单调递增。
• 单调递减的队列：在队列的基础上，时刻保持队列中的元素单调递减。

怎么做到？
• 除了队首可以出队外，新增一个在队尾出队的操作；
• 新元素要进队，先让不满足单调性的元素从队尾出队。

举个例子
• 元素是整数，单调递增的队列，允许重复元素
• 一开始是个空队列
• 数字 3进队                                 空队列，直接进队
• 数字 5进队                                 能保持单调性，直接进队
• 数字 8进队                                 能保持单调性，直接进队
• 数字 5进队                                 不能保持单调性，先将 8出队，再让 5进队
• 出队                                            数字 3出队
• 数字 9进队                                 能保持单调性，直接进队
• 数字 4进队                                 先让 5,5,9 都出队，再让 4进队
• 出队                                           数字 4出队

单调队列需要用到一个用C++ 自带的双端队列 deque，它可以从队首和队尾加入或删除元素。

deque<int> q;

性质 1：
• 一个元素进队时，从队尾删除了一些元素
• 删完后，自己入队之前，“先进队的元素中最后一个比自己小的”恰好在队尾
• 性质 2：
• 一个元素进队时，从队尾删除了一些元素
• 自己是它们的“后进队的元素中第一个比自己小的”

例题：

nkoj 2152

问题描述

给你一个长度为N(N<=10^6)的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，找出窗体所包含的数字的最大和最小值，如下表所示：k的值为3

讯享网窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 

输入格式

输出格式

共2行，第1行是每个位置的min value，第2行是每个位置的max value。

样例输入

样例输出

思路

单调递增队列，不允许重复元素
• 模拟滑动窗口，一步步滑动；
• 删除队尾比 𝑎𝑖大的数，它们没有用了，然后将 𝑎𝑖加入队尾；
• 如果队首是 𝑎𝑖−𝐾，它已经不再窗口内，也删除
• 队首元素就是当前窗口的最小值。
•最大值同理

代码

#include <bits/stdc++.h> using namespace std; deque<int> q; int a[]; int n,k; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ if(q.front()<=i-k) q.pop_front(); while(q.size()&&a[q.back()]>=a[i]) q.pop_back(); q.push_back(i); if(i>=k) cout<<a[q.front()]<<" "; } q.clear(); cout<<endl; for(int i=1;i<=n;i++){ if(q.front()<=i-k) q.pop_front(); while(q.size()&&a[q.back()]<=a[i]) q.pop_back(); q.push_back(i); if(i>=k) cout<<a[q.front()]<<" "; } return 0; }

nkoj 2149

讯享网

问题描述

FJ建立了一个布丁工厂。在接下来的N个星期里，原料牛奶和劳动力的价格会有很大波动。FJ希望能够在满足消费者需求的前提下尽量减小花费。
FJ预计接下来每个星期会需要Ci元钱来生产一单位布丁，且消费者会需要Pi单位布丁。
FJ每星期即可以生产布丁，也可以储存布丁供以后使用。它的仓库存储一星期一单位布丁需要S元钱。但是由于布丁有保质期，所以最多只能保存T星期。也就是说x星期生产的布丁可以在(x+T)星期销售，但是不能在(x+T+1)星期销售。
帮助FJ安排生产与存储的方案使得在满足消费者需求的前提下尽量减小花费。

输入格式

输出格式

仅一个数，即满足顾客需求前提下的最小花费。

样例输入

5 10 3
12 1
21 2
27 4
45 5
52 3

样例输出

488

思路

单调递增队列，不允许重复元素
• 模拟这一周的花费，一步步滑动；
• 删除队尾a[q.back()]+s*(i-q.back())<a[i]的数，它们不满足消费者需求，然后将i加入队尾；
• 如果队首是 小于i−T，它已经无法再售卖，也删除
• 队首即为最优方案
•累加队首输出

代码
 

讯享网#include <bits/stdc++.h> using namespace std; const int N=; int n,s,t,a[N],b[N]; long long ans; deque <int> q; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>s>>t; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } for(int i=1;i<=n;i++){ if(q.front()<i-t){ q.pop_front(); } while(!q.empty() && a[q.back()]+s*(i-q.back())>=a[i]){ q.pop_back(); } q.push_back(i); ans+=(a[q.front()]+s*(i-q.front()))*b[i]; } cout<<ans<<endl; return 0; }

 nkoj 5559

问题描述

数字录音中，声音是用表示空气压力的数字序列描述的，序列中的每个值称为一个采样，每个采样之间间隔一定的时间。
很多声音处理任务都需要将录到的声音分成由静音隔开的几段非静音段。
为了避免分成过多或者过少的非静音段，静音通常是这样定义的：m个采样的序列，该序列中采样的最大值和最小值之差不超过一个特定的阈值c。
请你写一个程序，检测n个采样中的静音。

输入格式

第一行有三个整数n，m，c，分别表示总的采样数、静音的长度和静音中允许的最大噪音程度。
第2行n个整数ai，表示声音的每个采样值，每两个整数之间用空格隔开。
1<=n<=， 1<=m<=10000， 0<=c<=10000
0<=ai<=1,000,000

输出格式

列出了所有静音的起始位置i
i满足max(a[i, . . . , i+m−1]) − min(a[i, . . . , i+m−1]) <= c
每行表示一段静音的起始位置，按照出现的先后顺序输出。
如果没有静音则输出NONE。

样例输入

样例输出

思路

单调递增队列，不允许重复元素

•两个单调队列，一个存区间最小，一个存区间最大
• 模拟静音段，一步步滑动
• 删除两个队尾不合法的数，然后将i加入队尾
• 如果(i-m)>=q.front()，不合法，删除两个队头
• 存两个队列队首的差

代码

#include <bits/stdc++.h> #define int long long using namespace std; deque<int> q; deque<int> p; int c,o; int a[]; int minn[]; int maxx[]; int n,m; int s,w=1; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>c; for(int i=1;i<=n;i++){ cin>>a[i]; while(!p.empty()&&a[i]<=a[p.back()]){ p.pop_back(); } while(!q.empty()&&a[i]>=a[q.back()]){ q.pop_back(); } q.push_back(i); p.push_back(i); while(!p.empty()&&(i-m)>=p.front()){ p.pop_front(); } while(!q.empty()&&(i-m)>=q.front()){ q.pop_front(); } if(i>=m){ minn[w]=a[p.front()]; maxx[w]=a[q.front()]; w++; } } for(int i=1;i<=w-1;i++){ if(maxx[i]-minn[i]<=c){ cout<<i<<endl; o++; } } if(o==0) cout<<"NONE"; return 0; }

完结撒花！！！

愿世界和平！！！