题意:
给一列数,用一个长度为k的区间在这列区间上从左到右移动,求出每个区间中的最大值和最小值。
要点:
单调队列,主要应用是存储最值,每次找最值只要看队头即可,否则每次都要遍历一次肯定超时。其实直接考单调队列的地方不多,主要是用它优化一些DP什么的。这题主要是注意一下因为区间更新,有时候队头会不在区间内,所以每次都要更新队头。
参考博客:点击打开链接
手造单调队列:
| 15410086 | Seasonal | 2823 | Accepted | 10972K | 5407MS | C++ | 1376B | 2016-04-19 14:44:41 |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1000001
int a[maxn], p[maxn];//记录下标
int min[maxn],max[maxn];
int q[maxn];
int n, k;void getmin()
{int i;int head = 1, rear = 0;for (i = 0; i < k-1; i++) //注意这里是k-1,每次第k个都要计算最值{while (head <= rear&&q[rear] >= a[i])rear--; //单调递增队列,如果队尾大于当前值,向前寻找比当前值小的数,插在它后面,并把后面删去q[++rear] = a[i];p[rear] = i; //记录队列中元素对应的的下标}for (; i < n; i++) //从第k-1个开始计算{while (head <= rear&&q[rear] >= a[i])rear--;q[++rear] = a[i];p[rear] = i;while (p[head] < i - k + 1)//如果队头元素下标小于区间范围,就删除对头元素{head++;}min[i - k + 1] = q[head];}
}
void getmax()
{int i;int head = 1, rear = 0;for (i = 0; i < k-1; i++){while (head <= rear&&q[rear] <= a[i])rear--; //单调递减队列,如果队尾元素小于当前值,向前寻找小于当前值的元素,插在其后并删除它后面的元素q[++rear] = a[i];p[rear] = i;}for (; i < n; i++){while (head <= rear&&q[rear] <= a[i])rear--;q[++rear] = a[i];p[rear] = i;while (p[head] < i - k + 1){head++;}max[i - k + 1] = q[head];}
}
void output()
{for (int i = 0; i < n - k + 1; i++)printf("%d%c", min[i], i == n - k ? '\n' : ' ');for (int i = 0; i < n - k + 1; i++)printf("%d%c", max[i], i == n - k ? '\n' : ' ');
}int main()
{scanf("%d%d", &n, &k);for (int i = 0; i < n; i++)scanf("%d", &a[i]);getmin();getmax();output();return 0;
}
优先队列STL:
| 15412473 | Seasonal | 2823 | Accepted | 18828K | 6000MS | C++ | 1014B | 2016-04-19 21:55:25 |
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 1000001
using namespace std;
int a[maxn];
int outmin[maxn], outmax[maxn];
int cnt1, cnt2;
int n, k;struct cmp1
{bool operator()(const int a1, const int a2)//运算符重载{return a[a1] > a[a2];}
};
struct cmp2
{bool operator()(const int a1, const int a2){return a[a1] < a[a2];}
};
priority_queue<int, vector<int>, cmp1> q1;//优先队列
priority_queue<int, vector<int>, cmp2> q2;int main()
{int i;scanf("%d%d", &n, &k);for (i = 1; i <= n; i++)scanf("%d", &a[i]);for (i = 1; i <= k-1; i++){q1.push(i);q2.push(i);}for (i = k; i <= n; i++){q1.push(i);q2.push(i);while (q1.top() <= i - k)q1.pop();outmin[cnt1++] = a[q1.top()];while (q2.top() <= i - k)q2.pop();outmax[cnt2++] = a[q2.top()];}for (i = 0; i < cnt1; i++){printf("%d%c", outmin[i], (i < n - k) ? ' ' : '\n');}for (i = 0; i < cnt2; i++){printf("%d%c", outmax[i], (i < n - k) ? ' ' : '\n');}return 0;
}