求m區間內的最小值
題目描述：
一個含有n項的數列(n<=2000000)，求出每一項前的m個數到它這個區間內的最小值，若前面的數不足m項則從第1個數開始，若前面沒有數則輸出0，
分析：
讀題之后可以發現，這道題就是在求：
給出一個長度為n的序列A，求A中所有長度為m的連續子序列中的最小值
而針對這種問題，單調佇列似乎是我們最好的選擇，
單調佇列，說是佇列，卻不符合佇列“先進先出”的原則，它只是沿用了佇列的思想，并具有一定的單調性，擁有一個佇列頭head和一個佇列尾tail，用head和tail來控制佇列的長度，篩選佇列中的元素以及保持佇列的單調性，
但怎樣控制佇列的長度，篩選佇列中的元素以及保持佇列的單調性呢？
這就是單調佇列的實作了，
用樣例來分析一下：
6 2
7 8 1 4 3 2
這樣，我們就擁有了一個初始佇列：7 8 1 4 3 2
擁有上帝視角的我們可以看出答案是：
0
7
7
1
1
3
這時候，我們發現，不論第一個元素是多少，它之前m個元素的最小值永遠為0（因為它之前并沒有元素）?，而最后一個元素是多少也沒有關系（因為它之后并沒有元素），
所以我們只用找到第2個到第n個元素中每個前m個元素的最小值就可以了，那么單調佇列的單調性也應該是遞增的，我們就可以把佇列里每個元素的序號放入單調佇列操作，就可以得到答案了，
于是我們可以開始模擬了：
考慮第一個元素，i=1，head=1，tail=0，q[tail]=0，a[1]=7，a[1]>a[ q[tail] ]，把a[1]放入不會破壞單調性，q[head]=0，這個元素距隊首元素的距離為0，則佇列為：1
考慮第二個元素，i=2，head=1，tail=1，q[tail]=1，a[2]=8，a[2]>a[ q[tail] ]，把a[2]放入不會破壞單調性，q[head]=1，這個元素距隊首元素的距離為1，則佇列為：1 2
考慮第三個元素，i=3，head=1，tail=2，q[tail]=2，a[3]=1，但a[3]<a[ q[tail] ]，把a[3]放入會破壞單調性，而a[3]<a[ q[tail] ]，由于求最小值，所以只能將a[ q[tail=2] ]彈出佇列來保證單調性了，而a[3]>a[ q[tail=1] ]，這時再將a[3]放入就不會破壞單調性了，q[head]=1，這個元素距隊首元素的距離為2，達到長度m=2了，這佇列頭head就向后移，則佇列為：3，
以此類推，直到第n-1個，因為第n個后面沒有元素，所以第n個不會進入佇列，每次都輸出佇列頭對應的元素值，就得到了答案，
代碼實作：
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 2000005
using namespace std;
int n,m;
int a[maxn];
int q[maxn];
int head,tail;
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
head=1;
tail=0;
printf("0\n");//第一個元素它之前并沒有元素
for(int i=1;i<n;i++)//從1~n-1個，第n個不進佇列
{
while((head<=tail)&&((i-q[head])>=m)) head++;//控制佇列的長度
while((head<=tail)&&(a[q[tail]]>=a[i])) tail--;//篩選佇列中的元素
tail++;
q[tail]=i;//保持佇列的單調性
printf("%d\n",a[q[head]]);//輸出答案
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/79239.html
標籤：C++
下一篇：回傳指標的函式