网站软件设计,广州有什么好玩的游乐场,win7用本地文件做网站模板,请人开发网站多少钱例题
有一个长为 n 的序列 a#xff0c;以及一个大小为 k 的窗口。现在这个从左边开始向右滑动#xff0c;每次滑动一个单位#xff0c;求出每次滑动后窗口中的最大值和最小值。
例如#xff1a;
The array is [1,3,−1,−3,5,3,6,7],and k3。 输入格式
输入一共有两行…例题
有一个长为 n 的序列 a以及一个大小为 k 的窗口。现在这个从左边开始向右滑动每次滑动一个单位求出每次滑动后窗口中的最大值和最小值。
例如
The array is [1,3,−1,−3,5,3,6,7],and k3。 输入格式
输入一共有两行第一行有两个正整数 n,k。 第二行 n 个整数表示序列 a
输出格式
输出共两行第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值
输入输出样例
输入
8 3
1 3 -1 -3 5 3 6 7
输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明/提示
【数据范围】 对于 50%50% 的数据1≤n≤105 对于 100%100% 的数据1≤k≤n≤106ai∈[−2^31,2^31)。
代码实现
#includeiostream
#includequeue
using namespace std;
const int N1e610;
int a[N],b[N],ans1[N],ans2[N];int main(){int n,m,c0;cinnm;dequeints1,s2;for(int i1;in;i){scanf(%d,a[i]);b[i]a[i];while(s1.size()a[s1.back()]a[i])s1.pop_back();while(s2.size()b[s2.back()]b[i])s2.pop_back();s1.push_back(i);s2.push_back(i);while(s1.front()i-m)s1.pop_front();while(s2.front()i-m)s2.pop_front();if(im){ans1[c]a[s1.front()];ans2[c]b[s2.front()];}}for(int i1;ic;i)coutans1[i] ;coutendl;for(int i1;ic;i)coutans2[i] ;coutendl;return 0;
}
滑动窗口模板
//求窗口内的最小值
dequeintq;
for(int i1;in;i){scanf(%d,a[i]);//如果新元素小于尾部元素就把尾部元素删除 while(q.size()a[q.back()]a[i])q.pop_back();//把新元素的下标加入队列尾部q.push_back(i); //如果第一个元素的下标超出窗口范围就把第一个元素删除 while(q.front()i-m)q.pop_front(); if(im)printf(%d\n,a[q.front()]); }
双端队列常用操作
deque 容器的成员函数 函数成员函数功能begin()返回指向容器中第一个元素的迭代器。end()返回指向容器最后一个元素所在位置后一个位置的迭代器通常和 begin() 结合使用。rbegin()返回指向最后一个元素的迭代器。rend()返回指向第一个元素所在位置前一个位置的迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。size()返回实际元素个数。max_size()返回容器所能容纳元素个数的最大值。这通常是一个很大的值一般是 232-1我们很少会用到这个函数。resize()改变实际元素的个数。empty()判断容器中是否有元素若无元素则返回 true反之返回 false。shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。at()使用经过边界检查的索引访问元素。front()返回第一个元素的引用。back()返回最后一个元素的引用。assign()用新元素替换原有内容。push_back()在序列的尾部添加一个元素。push_front()在序列的头部添加一个元素。pop_back()移除容器尾部的元素。pop_front()移除容器头部的元素。insert()在指定的位置插入一个或多个元素。erase()移除一个元素或一段元素。clear()移出所有的元素容器大小变为 0。swap()交换两个容器的所有元素。emplace()在指定的位置直接生成一个元素。emplace_front()在容器头部生成一个元素。和 push_front() 的区别是该函数直接在容器头部构造元素省去了复制移动元素的过程。emplace_back()在容器尾部生成一个元素。和 push_back() 的区别是该函数直接在容器尾部构造元素省去了复制移动元素的过程。
