單調佇列~~~~
同時食用效果更佳
1.單調佇列可以干嘛？
求區間最值
好像就沒啥了
2.不過我們簡單舉個例子——
玩卡牌類游戲的時候，每個角色有對應的絕對戰力值，但玩家選角色上陣的時候有時不只是會看每個角色的絕對戰力值 還會看好不好看啥的 （lsp了）
對于那些 又丑又弱 的角色，玩家是絕對不會選的
單調佇列就是這個思想
一組資料中，取區間極值，如果某個值的下標小，又取不到極值，那肯定是看都不會選的（簡而言之就是在這個值所在的區間中，它永遠取不到極值那么就可以徹底排除了）
3.直接上模板代碼
//陣列實作
#include <cstdio>
#define MAXN 2000005
using namespace std;
struct Num{
int index,x;//需要記錄單調佇列內每個數的入隊時間(index)和大小(x)
};
int a[MAXN]; //原陣列
Num q[MAXN]; //單調佇列
int main(void){
int n,m; //n表示序列長度，m表示滑動視窗長度
int front,back; //front,back分別表示隊頭、隊尾位置
//輸入
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
//問題解決
front=1;
back=0;//初始化隊頭隊尾位置，隊頭>隊尾表示隊空
for (int i=1;i<=n;i++){
//先輸出數a[i]前的最小值
if (front>back) //q空，即a[i]前沒有元素
printf("0\n");
else { //否則判斷隊頭是否需要出隊并輸出范圍內的隊頭
if (q[front].index+m<i) //隊頭已經超出滑動視窗范圍
front++; // 彈出隊頭
printf("%d\n",q[front].x); //此時隊一定非空（想想為什么）
}
while (front<=back && q[back].x>=a[i])
//當佇列非空時，不斷彈出隊尾比當前元素大的元素
back--;
back++;
q[back].x=a[i];
q[back].index=i;//將當前元素入隊
//注意：當前元素無論如何都會入隊（想想為什么）
}
return 0;
}
4.來道例題
原題洛谷P1714
決議
區間最值前綴和走一波
所以我們要求的就是
max(sum[i]-sum[j])
(j是以i為起點的，在區間范圍內可能的所有點，此時與每一個i來說，sum[i]是固定的，所以就是求min(s[j]))所以代碼就出來了,有點貪心的味道
正解代碼如下：
#include<cstdio>
#include<iostream>
using namespace std;
const int N=5e5+10,INF=1e9;
int sum[N],q[N];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for (register int i=1;i<=n;++i)
{
int x;scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
int head=1,tail=1,ans=-INF;q[1]=0;
for (register int i=1;i<=n;++i)
{
while (head<=tail&&q[head]<i-m) head++;//已經不在范圍內要出隊
ans=max(ans,sum[i]-sum[q[head]]);
while (head<=tail&&sum[i]<=sum[q[tail]]) tail--;//維護單調遞增的佇列
q[++tail]=i;
}
printf("%d\n",ans);
return 0;
}
the end
參考：
https://www.luogu.com.cn/blog/Sweetlemon/dan-diao-dui-lie
https://www.luogu.com.cn/blog/user28920/solution-p1714
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145107.html
標籤：其他