題目大意：給你n個數，求出每個數前m位的最小值

題解：單調隊列，用一個可以雙向彈出的隊列來存一串數，滿足里面的數具有單調性，我們可以假設它是單調遞增的，即求最小的數。那么可以把要插入的這個數與隊尾元素比較，如果隊尾的數大，那么插入它就不滿足單調性了，那么我們就從隊尾刪除元素，直到比隊尾元素大。這樣就可以滿足要求。如果隊首元素已經超出了m的范圍，就從隊首刪除元素，隊首的元素就一直是答案。

?

#include<cstdio> using namespace std; int n,m; int q[2001000],h,t; int s[2001000]; int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&s[i]);puts("0");q[h=t=1]=1;for (int i=2;i<=n;i++){if (i-q[h]>m)h++;printf("%d\n",s[q[h]]);while (h<=t&&s[i]<s[q[t]])t--;q[++t]=i;}return 0; }

?

轉載于:https://www.cnblogs.com/Memory-of-winter/p/7811283.html

總結

以上是生活随笔為你收集整理的[洛谷P1440]求m区间内的最小值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。