十分不良的过来复制题面qwq
题目描述
有一个 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。
复制完了qwq
−−−−−−−−−−−−−−−−−−下面放上代码−−−−−−−−−−−−−−−−−−−
code
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <deque>
#define maxn 2000005
using namespace std ;
int n , m , k , a[maxn] ;
deque<int>q ;
int read() ;
int main () {
n = read() , k = read() ;
for(int i = 1 ; i <= n ; i ++) {
a[i] = read () ;
}
for(int i = 1 ; i <= n ; i ++) {
while(!q.empty() && a[q.back()] <= a[i]) q.pop_back() ;
while(!q.empty() && i-q.front()+1 > k) q.pop_front() ;
q.push_back(i) ;
if(i >= k) cout << a[q.front()] <<endl ;
}
return 0 ;
}
int read() {
int x = 0 , f = 1 ;char s = getchar () ;
while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar () ;}
while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar () ;}
return x * f ;
}
非stl版本
code
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std ;
int n , m , k ;
typedef pair<int,int>pa ;
int q[2000010] ;
int a[2000010] ;
int head = 0 , tail = 1 ;
int main(){
scanf("%d%d",&n,&k) ;
scanf("%d",&a[1]) ;
q[++tail] = 1 ;
for(int i = 2; i <= n; i++)
{
scanf("%d", &a[i]);
while(head <= tail && a[i] > a[q[tail]]) tail--;
q[++tail] = i;
if(i - q[head] == k) head++;
if(i >= k) printf("%d\n", a[q[head]]);
}
}