洛谷 P2032 扫描 题解
2024-08-21 12:22:05
P2032 扫描
题目描述
有一个 1 ∗ n 的矩阵，有 n 个正整数。
现在给你一个可以盖住连续的 k 的数的木板。
一开始木板盖住了矩阵的第 1 ∼ k 个数，每次将木板向右移动一个单位，直到右端与第 n 个数重合。
每次移动前输出被覆盖住的最大的数是多少。
输入格式
第一行两个数，n，k，表示共有 n 个数，木板可以盖住 k 个数。
第二行 n 个数，表示矩阵中的元素。
输出格式
共 n − k + 1 行，每行一个正整数。
第 i 行表示第 i ∼ i + k − 1 个数中最大值是多少。
输入输出样例
输入 #1
5 3
1 5 3 4 2
输出 #1
5
5
4
说明/提示
对于 20% 的数据保证：1 ≤ n ≤ 1e3，1 ≤ k ≤ n
对于 50% 的数据保证：1 ≤ n ≤ 1e4，1 ≤ k ≤ n
对于 100% 的数据保证：1 ≤ n ≤ 2 ∗ 1e6，1 ≤ k ≤ n
矩阵中元素大小不超过 1e4。
【思路】
单调队列
手写单调队列有点双指针的意思
从第一个开始枚举
如果队首的数超出了k区间的距离限制就将队尾弹出
直到队首符合在k区间内的要求
如果队尾的值比这个要插入的值还小
那这个队尾是不可能被输出的
他比我小还比我强！这让我怎么活！所以弹出我吧！
处理完成之后
每一个k区间需要输出的值就是他的队首
因为这是一个递减的区间
【完整代码】
#include<iostream>
#include<cstdio>
using namespace std;
const int Max = 2000006;
int a[Max];
int q[Max];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(register int i = 1;i <= n;++ i)
scanf("%d",&a[i]);
int t = 0,w = 1;
for(register int i = 1;i <= n;++ i)
{
while(t <= w && q[t] + k <= i)t ++;
while(t <= w && a[q[w]] < a[i])w--;
q[++ w] = i;
if(i >= k)
cout << a[q[t]] << endl;
}
return 0;
}
最新文章
- 极光推送和友盟推送，ios端和安卓端的后端调试设置
- 在测试框架中使用Log4J 2
- javascript 设计模式-----单例模式
- String,StringBuffer与StringBuilder的区别??[转]
- Add Binary
- MyEclipse------PreparedStatement使用方法
- 对java面试文章的技术漫谈的C#技术理解
- C. Tavas and Karafs 二分查找+贪心
- Delphi 函数指针（三大好处：灵活，委托的本质，回调机制），还可把函数指针当参数传入
- Mac OS提示＃ 14：自己定义文件图标
- Nutch 二次开发parse纸
- Java的“影子克隆”和“深度克隆”
- 《java入门第一季》之Arrays类前传（排序问题）
- ImageMagick
- Web API2 使用EF Code Migrations to Seed DB
- 【BZOJ1152】歌唱王国（生成函数，KMP）
- linux （centOS）安装 oracle 11g 以及卸载oracle
- (网页)logback的使用和logback.xml详解(转)
- day19(乱码解决方案)
- Docker-删除untagged docker images