「NOIP模拟赛」滑动的窗户
「题目描述」
在一个包含n个元素的数组上，有一个长度为k的窗户在从左向右滑动。窗户每滑动到一个位置，我们都可以看到k个元素在窗户中。如下的例子所示，假设数组为 [1 3 -1 -3 5 3 6 7]，而k等于3:
|
窗户位置 |
最小值 |
最大值 |
|
[1 3 -1] -3 5 3 6 7 |
-1 |
3 |
|
1 [3 -1 -3] 5 3 6 7 |
-3 |
3 |
|
1 3 [-1 -3 5] 3 6 7 |
-3 |
5 |
|
1 3 -1 [-3 5 3] 6 7 |
-3 |
5 |
|
1 3 -1 -3 [5 3 6] 7 |
3 |
6 |
|
1 3 -1 -3 5 [3 6 7] |
3 |
7 |
对于窗户滑动过的每个位置，请给出窗户内k个元素的最小值和最大值。
「输入」
输入文件：window.in
输入的第一行包括两个整数n，k，n表示数组的长度，k表示窗户的长度。
接下来一行包括n个整数，表示这个n个元素的数组。
「输出」
输出文件：window.out
输出包含两行，每行包括n-k+1个整数，第一行表示窗户从左到右滑动过程中的最小值，第二行表示窗户从左到右滑动过程中的最大值。
「输入样例」
8 3
1 3 -1 -3 5 3 6 7
「输出样例」
-1 -3 -3 -3 3 3
3 3 5 5 6 7
「数据范围」
对于100%的数据，3<=n<=1000000，1<=k<=n，数组中的每个元素均在int范围内
题解
这个经典的单调队列吧，娱乐的话堆也是可以的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K; int a[1000005]; int q1[1000005],q2[1000005]; int ans1[1000005],ans2[1000005]; int l1=1,l2=1,r1,r2; int main() { //freopen("window.in","r",stdin); //freopen("window.out","w",stdout); n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++) { while(l1<=r1&&q1[l1]<=i-K)l1++; while(l2<=r2&&q2[l2]<=i-K)l2++; while(l1<=r1&&a[i]<a[q1[r1]])r1--; q1[++r1]=i; while(l2<=r2&&a[i]>a[q2[r2]])r2--; q2[++r2]=i; ans1[i]=a[q1[l1]]; ans2[i]=a[q2[l2]]; } for(int i=K;i<=n;i++)printf("%d ",ans1[i]); puts(""); for(int i=K;i<=n;i++)printf("%d ",ans2[i]); return 0; } |
Subscribe
计数器 9863303
OI 课件=>
OI 课件=>