当前位置: 首页 > news >正文

加拿大28网站开发百度营销推广官网

加拿大28网站开发,百度营销推广官网,鱼台建设局网站,查看wordpress密码Description 有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 例如: The array is [1,3,−1,−3,5,3,6,7] and k3。 Input 输入一共有…

Description

有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

例如:

The array is [1,3,−1,−3,5,3,6,7] and k=3。

Input

输入一共有两行,第一行有两个正整数 n,k。
第二行 n 个整数,表示序列 a

Output

输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

Sample 1

InputcopyOutputcopy
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7

Hint

【数据范围】
对于50% 的数据,1≤n≤10^5;
对于100% 的数据,1≤k≤n≤10^6,ai​∈[−231,231)。

 

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], maxq[N], minq[N];
int n, m;//h是队头,用于输出答案;t是队尾,用于加入和删除元素
//注意:对头为左,队尾为右,队头只出,队尾可出可进;因此若队内有元素,则h<=t
//max队内的元素因保持单调递减的性质,加入的不是元素值,而是元素所在数组a中的下标
void maxfind() {int h = 0, t = -1;for (int i = 1; i <= n; i++){if (h <= t && maxq[h] <= i - m) h++;    //不在当前滑动窗口的元素删除while (h <= t && a[i] >= a[maxq[t]]) t--; //a[i]为当前元素,若当前元素大于队尾的元素,则需要删除,时其满足单调递减的性质maxq[++t] = i;   //加入新元素的下标if(i>=m) cout << a[maxq[h]] << " ";//输出结果}
}
//原理同上
void minfind() {int h = 0, t = -1;for (int i = 1; i <= n; i++){if (h <= t && minq[h] <= i - m) h++;while (h <= t && a[i] <= a[minq[t]]) t--;minq[++t] = i;if(i>=m) cout << a[minq[h]] << " ";}
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];minfind();cout << endl;maxfind();return 0;
}

 单调队列模板(滑动窗口)_滑动窗口 /【模板】单调队列_胡牧之.的博客-CSDN博客

http://www.laogonggong.com/news/46.html

相关文章:

  • 河南网站建设软件百度排名点击软件
  • 做国珍新时代 网站网络营销期末考试题库
  • 当今做网站的流行互联网推广平台有哪些公司
  • 三合一企业网站模板网页浏览器
  • 比较好的网站设计公司怎样看网页的友情链接
  • 宁波做外贸网站一键生成app制作器
  • info哪个网站续费便宜seo综合查询站长工具关键词
  • seo系统源码西安seo关键字优化
  • 校际凡科平台是干什么的网站建设排名优化
  • 企业网站建设选题的依据及意义b2b平台推广
  • 手机网站开发下拉刷新青岛网络优化哪家专业
  • 查询备案网站上海搜索优化推广
  • 凡科做的网站被举报了会怎么样2023年6月疫情恢复
  • 龙岗外贸网站建设公司百度搜索热度
  • 人大门户网站建设解决方案百度广告大全
  • 网站建设 APP开发销售怎么做seo做的比较牛的公司
  • 怎么制作图片加文字带声音的视频谷歌seo网站排名优化
  • 商业网站设计方案今天特大新闻
  • 专业网站设计制作优化排名新产品的推广销售方法
  • 广州网站改版设计搜索引擎推广seo
  • 潜江做网站的公司有哪些百度查询入口
  • 向搜索引擎提交网站自己如何做一个网站
  • flash网站设计概述域名购买平台
  • 知名网站制作公司青岛分公司郑州网站推广优化
  • 南京网站建设企业深圳seo网络推广
  • 设计院都是带编制的吗优化模型数学建模
  • 建材行业门户网站源码快速网站推广
  • 吴中区两学一做网站seo 视频
  • Wordpress1002无标题搜外seo
  • 做招聘求职网站线上购买链接