首页 > 代码库 > POJ 2823 Sliding Window（单调队列）
POJ 2823 Sliding Window（单调队列）
【题目链接】 http://poj.org/problem?id=2823
【题目大意】
给出一个数列，问每k个数总最小值和最大值分别是多少
【题解】
单调队列顺序维护需求，时间节点超过k的点就出队
我们维护两次单调队列，用xor的小trick可以降低码量。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int MAX_N=1000010; int n,k; int a[MAX_N],b[MAX_N],deq[MAX_N];void solve(int u){ int s=0,t=0; for(int i=0;i<n;i++){ while(s<t&&((a[deq[t-1]]>a[i])^u||a[deq[t-1]]==a[i]))t--; deq[t++]=i; if(i-k+1>=0){ b[i-k+1]=a[deq[s]]; if(deq[s]==i-k+1)s++; } }for(int i=0;i<=n-k;i++)printf("%d%c",b[i],i==n-k?‘\n‘:‘ ‘);}int main(){ while(~scanf("%d%d",&n,&k)){ for(int i=0;i<n;i++)scanf("%d",&a[i]); solve(0); solve(1); }return 0;}POJ 2823 Sliding Window（单调队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。