【POJ2823】Sliding Window
标签：一个 style mes space 位置 int stream iostream poj
http://poj.org/problem?id=2823
题意：你有一个长度n的序列，分别询问[1,k],[2,k+1],[3,k+2],...,[n-k+1,n]这n-k+1个区间的最大值和最小值。
单调队列入门题。用两个单调队列分别维护当前最大值和最小值的最优解、次优解、……K优解。
每次拓展一个数就不断将队尾的劣解出队，保持队列的单调性。然后不断将队首的过气解（即距离当前位置大于等于k）出队。之后队列的队首就是最优解了。
#include
#include #define maxn 1000005
using namespace std;
int n, k, a[maxn];
dequeint> mx, mn; // 分别存最大值的最优解和最小值的最优解
int mxans[maxn], mnans[maxn];
int main()
{
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i )
cin >> a[i];
for (int i = 1; i // 先处理前k-1个数
{
// 将队尾的劣解出队
while (!mn.empty() && a[mn.back()] > a[i])
mn.pop_back();
mn.push_back(i);
while (!mx.empty() && a[mx.back()] a[i])
mx.pop_back();
mx.push_back(i); // 插入当前解
}
for (int i = k; i )
{
// 将队尾的劣解出队
while (!mn.empty() && a[mn.back()] > a[i])
mn.pop_back();
mn.push_back(i);
while (!mx.empty() && a[mx.back()] a[i])
mx.pop_back();
mx.push_back(i);
// 将队首的过气解出队
while (!mx.empty() && i - mx.front() >= k)
mx.pop_front();
while (!mn.empty() && i - mn.front() >= k)
mn.pop_front();
mxans[i] = mx.front();
mnans[i] = mn.front();
}
for (int i = k; i )
cout ‘ ‘;
cout endl;
for (int i = k; i )
cout ‘ ‘;
cout endl;
return 0;
}
【POJ2823】Sliding Window
标签：一个 style mes space 位置 int stream iostream poj
原文地址：http://www.cnblogs.com/ssttkkl/p/7625920.html
评论