SICKO @ 2023-12-04 17:39:36
这是代码捏
#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
const int N = 1e6+6;
deque<int> my_queue;
int num[N];
vector<int> min_ans;
vector<int> max_ans;
int main()
{
int n, m; cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>num[i];
}
if(m == 1)
{
for(int i=1; i<=n; i++) cout<<num[i]<<" ";
cout<<"\n";
for(int i=1; i<=n; i++) cout<<num[i]<<" ";
return 0;
}
//--------------------------------------------------------------------------------------------------------------------
// 滑动窗口，处理最大值问题，则维护一个单调递减的队列
// 预处理第一步，队列里面得有东西
my_queue.push_back(1);
// 预处理第二步，留下有可能成为最大值的值的地址
for(int i=2; i<m; i++)
{
// 如果这个值比队尾的值要小或相等，那么队尾的值有可能成为之后区间的最大值，这个值也是，所以我们入队
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
}
// 如果这个值比队尾的值要大，那么队尾的值一定不可能成为之后区间的最大值了，我们就后端出列直到空或者符合小于等于
else while(true)
{
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
}
// 主处理函数
for(int i=m; i<=n; i++)
{
// 再重复一遍之前的处理
// 如果这个值比队尾的值要小或相等，那么队尾的值有可能成为之后区间的最大值，这个值也是，所以我们入队
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
}
// 如果这个值比队尾的值要大，那么队尾的值一定不可能成为之后区间的最大值了，我们就后端出列直到空或者符合小于等于
else while(true)
{
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
// 最后别忘了判断队头是否合法。怎么判断，如果这个队头加上 m 的值小于等于当前位置，那么说明队头不在窗口内
if(my_queue.front()+m<=i) my_queue.pop_front();
// 到了主处理函数处，我们就可以判断最大最小值了，按照之前的处理，最大值一定会出现在对头
max_ans.push_back(num[my_queue.front()]);
}
//---------------------------------------------------------------------------------------------------------------------
// 接下来就是处理最小值问题了，最小值问题，我们就得维护单调递增的队列
// 别忘了清空队列
my_queue.clear();
// 预处理第一步，队列里面得有东西
my_queue.push_back(1);
// 预处理第二步，留下有可能成为最小值的值
for(int i=2; i<m; i++)
{
// 如果这个值比队尾的要大或者相等，那么说明这两值有可能成为之后的最小值，我们加到队列里面
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
}
else while(true)
{
// 否则队尾一定不可能成为之后区间的最小值，我们不断弹出队尾直到找到目标
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
}
// 主处理
for(int i=m; i<=n; i++)
{
// 照搬之前操作
// 如果这个值比队尾的要大或者相等，那么说明这两值有可能成为之后的最小值，我们加到队列里面
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
}
else while(true)
{
// 否则队尾一定不可能成为之后区间的最小值，我们不断弹出队尾直到找到目标
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
// 别忘了判断队头是否合法。怎么判断，如果这个队头加上 m 的值小于等于当前位置，那么说明队头不在窗口内
if(my_queue.front()+m<=i) my_queue.pop_front();
// 到了主处理函数处，我们就可以判断最大最小值了，按照之前的处理，最小值一定会出现在对头
min_ans.push_back(num[my_queue.front()]);
}
// 输出答案
for(int i:min_ans)
{
cout<<i<<" ";
}
cout<<"\n";
for(int i:max_ans)
{
cout<<i<<" ";
}
return 0;
}测试点 3 是
很神奇的地方在于如果不加开头 if(m==1) 的判断会 WA on 3，但实际上去做其他题并不会出现这样子的情况
比如P2032 扫描，P2251 质量检测， 1084: 滑动窗口
求大佬帮帮
by SICKO @ 2023-12-04 17:44:42
实际上输出的结果也是一样的
by SICKO @ 2023-12-05 21:23:02
已解决，
#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
const int N = 1e6+6;
deque<int> my_queue;
int num[N];
vector<int> min_ans;
vector<int> max_ans;
int main()
{
int n, m; cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>num[i];
}
// if(m == 1)
// {
// for(int i=1; i<=n; i++) cout<<num[i]<<" ";
// cout<<"\n";
// for(int i=1; i<=n; i++) cout<<num[i]<<" ";
// return 0;
// }
//--------------------------------------------------------------------------------------------------------------------
// 滑动窗口，处理最大值问题，则维护一个单调递减的队列
// 预处理第一步，队列里面得有东西
my_queue.push_back(1);
// 预处理第二步，留下有可能成为最大值的值的地址
for(int i=2; i<m; i++)
{
// 如果这个值比队尾的值要小或相等，那么队尾的值有可能成为之后区间的最大值，这个值也是，所以我们入队
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
}
// 如果这个值比队尾的值要大，那么队尾的值一定不可能成为之后区间的最大值了，我们就后端出列直到空或者符合小于等于
else while(true)
{
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
}
// 主处理函数
for(int i=m; i<=n; i++)
{
// 再重复一遍之前的处理
// 如果这个值比队尾的值要小或相等，那么队尾的值有可能成为之后区间的最大值，这个值也是，所以我们入队
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
}
// 如果这个值比队尾的值要大，那么队尾的值一定不可能成为之后区间的最大值了，我们就后端出列直到空或者符合小于等于
else while(true)
{
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] <= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
// 最后别忘了判断队头是否合法。怎么判断，如果这个队头加上 m 的值小于等于当前位置，那么说明队头不在窗口内
while(my_queue.front()+m<=i) my_queue.pop_front();
// 到了主处理函数处，我们就可以判断最大最小值了，按照之前的处理，最大值一定会出现在对头
max_ans.push_back(num[my_queue.front()]);
}
//---------------------------------------------------------------------------------------------------------------------
// 接下来就是处理最小值问题了，最小值问题，我们就得维护单调递增的队列
// 别忘了清空队列
my_queue.clear();
// 预处理第一步，队列里面得有东西
my_queue.push_back(1);
// 预处理第二步，留下有可能成为最小值的值
for(int i=2; i<m; i++)
{
// 如果这个值比队尾的要大或者相等，那么说明这两值有可能成为之后的最小值，我们加到队列里面
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
}
else while(true)
{
// 否则队尾一定不可能成为之后区间的最小值，我们不断弹出队尾直到找到目标
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
}
// 主处理
for(int i=m; i<=n; i++)
{
// 照搬之前操作
// 如果这个值比队尾的要大或者相等，那么说明这两值有可能成为之后的最小值，我们加到队列里面
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
}
else while(true)
{
// 否则队尾一定不可能成为之后区间的最小值，我们不断弹出队尾直到找到目标
my_queue.pop_back();
if(my_queue.empty())
{
my_queue.push_back(i);
break;
}
if(num[i] >= num[my_queue.back()])
{
my_queue.push_back(i);
break;
}
}
// 别忘了判断队头是否合法。怎么判断，如果这个队头加上 m 的值小于等于当前位置，那么说明队头不在窗口内
while(my_queue.front()+m<=i) my_queue.pop_front();
// 到了主处理函数处，我们就可以判断最大最小值了，按照之前的处理，最小值一定会出现在对头
min_ans.push_back(num[my_queue.front()]);
}
// 输出答案
for(int i:min_ans)
{
cout<<i<<" ";
}
cout<<"\n";
for(int i:max_ans)
{
cout<<i<<" ";
}
return 0;
}把 if 判断方法改为 while 即可。