ZJYYCOJ-会移动的盒子

题目链接: http://acm.oinsm.com/problem.php?cid=1031&pid=4

在这里插入图片描述

思路

滑动窗口的题,周赛的时候,读懂这题,就感觉似曾相识,所以当时可以想到需要去维护一个单调性,然后自己就傻傻的去用优先队列来维护了,压根就是忘掉了单调性这个概念了!(QAQ…
首先,能想到用队列来实现,但是考虑到用从后放,从前取出,所以得用deque来实现,维护一次递减,一次递增即可!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int num[MAXN];
int main(){
ios::sync_with_stdio(false);
int n, m;
while(cin >> n >> m) {
for(int i = 1; i <= n; i++) cin >> num[i];
deque<int> q;
// 最小值
for(int i = 1; i <= n; i++) {
while(!q.empty() && q.front() <= (i - m)) {
q.pop_front();
}
while(!q.empty() && num[q.back()] >= num[i]){
q.pop_back();
}
q.push_back(i);
if(i >= m) {
if(i != m) cout << " ";
cout << num[q.front()];
}
}
cout << endl;
while(!q.empty()) {
q.pop_front();
}
// 最大值
for(int i = 1; i <= n; i++) {
while(!q.empty() && q.front() <= (i - m)) {
q.pop_front();
}
while(!q.empty() && num[q.back()] <= num[i]){
q.pop_back();
}
q.push_back(i);
if(i >= m) {
if(i != m) cout << " ";
cout << num[q.front()];
}
}
cout << endl;
}
return 0;
}

附上以前写的相同例题

https://blog.csdn.net/HKer_YM/article/details/100417332

本文标题:ZJYYCOJ-会移动的盒子

文章作者:HKer_YM

发布时间:2020年03月16日 - 12:14:45

最后更新:2020年03月16日 - 12:15:48

原始链接:https://blog.dreams-wj.top/2020/03/16/ZJYYCOJ-%E4%BC%9A%E7%A7%BB%E5%8A%A8%E7%9A%84%E7%9B%92%E5%AD%90/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。