Mosklia @ 2018-06-07 11:03:25
如题,使用STL的deque实现的单调队列
可是RE
求教?
#include<cstdio>
#include<queue>
using namespace std;
template<typename comp>
struct Que{
deque<int> elem;
comp cmp;
void push(int v){
while(elem.size()){
if(cmp(elem.back(), v))
elem.pop_back();
else break;
// puts("inserting elems");
}
elem.push_back(v);
}
void pop(){
elem.pop_front();
}
int front(){
return elem.front();
}
bool empty(){
return elem.empty();
}
int size(){
return elem.size();
}
};
Que<greater<int> > q1;
Que<less<int> > q2;
queue<int> ans_min, ans_max;
int a[100000+5];
int main(){
int n, k;
scanf("%d %d", &n, &k);
for(int i = 1; i <= k; ++i){
int step;
scanf("%d", &step);
a[i] = step;
// puts("Ok");
q1.push(step);
q2.push(step);
}
ans_min.push(q1.front());ans_max.push(q2.front());
for(int i = k+1; i <= n; ++i) scanf("%d", a+i);
for(int i = k+1; i <= n; ++i){
if(q1.front() == a[i-k]) q1.pop();
if(q2.front() == a[i-k]) q2.pop();
q1.push(a[i]);q2.push(a[i]);
ans_min.push(q1.front());
ans_max.push(q2.front());
}
while(ans_min.size())
printf("%d ", ans_min.front()),
ans_min.pop();
putchar('\n');
while(ans_max.size())
printf("%d ", ans_max.front()),
ans_max.pop();
return 0;
}
by AThousandSuns @ 2018-06-07 11:32:05
@Sparky_14145 注意数据范围……
by Mosklia @ 2018-06-07 13:26:32
@AThousandSuns 谢谢
写错数据范围,找了半天没找到Bug。。尴尬