首页 > 代码库 > poj2823
poj2823
题目：An array of size n ≤ 10^6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and k is 3.
输入：The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
输出：There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
样例输入： 8 3 1 3 -1 -3 5 3 6 7
样例输出： -1 -3 -3 -3 3 3 3 3 5 5 6 7
题目大意：给定n个数字，告诉你一个可移动的区间长度k，即一个会滑动的窗口，求被窗口包围的数字的最大值和最小值。 题解：啊这题是经典问题。。。首先我觉得可以用线段树写啊这应该是比较正常且扎实的方法吧，这题不就是线段树求rmq吗。。但是我觉得10^6好像有点要卡常？？这题其实是一道非常水的单调队列啦，我为了能好好学习dp优化才开始学的（误）从题意就可以显而易见地看出来这就是裸的单调队列，所以本题就是裸的单调队列，时空都是O(N)。
传教环节：
1 /* 2 ━━━━━┒ギリギリ♂ eye！ 3 ┓┏┓┏┓┃キリキリ♂ mind！ 4 ┛┗┛┗┛┃＼○／ 5 ┓┏┓┏┓┃ / 6 ┛┗┛┗┛┃ノ) 7 ┓┏┓┏┓┃ 8 ┛┗┛┗┛┃ 9 ┓┏┓┏┓┃10 ┛┗┛┗┛┃11 ┓┏┓┏┓┃12 ┛┗┛┗┛┃13 ┓┏┓┏┓┃14 ┃┃┃┃┃┃15 ┻┻┻┻┻┻16 */17 #include <iostream>18 #include <algorithm>19 #include <stdio.h>20 #include <cmath>21 #include <string>22 #include <string.h>23 #include <numeric>24 #define REM main25 using namespace std;26 int n,k;27 int a[1000000+2];28 int que_1[1000000+2];29 int que_2[1000000+2];30 int p[1000000+2];31 int p2[1000000+2];32 int maxx[1000000+2];33 int minn[1000000+2];34 /*int read()35 {36 int p=1,x;37 char c;38 while((c=getchar())<‘0‘||c>‘9‘)39 if(c==‘-‘)40 p=-1;41 x=c-‘0‘;42 while((c=getchar())>=‘0‘&&c<=‘9‘)43 x=x*10+c-‘0‘;44 x*=p;45 return x;46 }*/47 //这个读入优化坑了我无数次了然后我生气了把这个删了重打QAQ。。。48 int REM()49 {50 cin.sync_with_stdio(false);51 cin>>n>>k;52 int i;53 for (i=1;i<=n;i++)54 scanf("%d",&a[i]);55 int head=1,tail=0;56 for (i=1;i<=k;i++)57 {58 while(head<=tail && que_1[tail]>=a[i])59 tail--;60 que_1[++tail]=a[i];61 p[tail]=i;62 }63 cout<<que_1[head]<<" ";64 for (i;i<=n;i++)65 {66 while(head<=tail && que_1[tail]>=a[i])67 tail--;68 que_1[++tail]=a[i];69 p[tail]=i;70 while(p[head]<=i-k)71 head++;72 cout<<que_1[head]<<" ";73 }74 75 cout<<endl;76 head=1,tail=0;77 for (i=1;i<=k;i++)78 {79 while(head<=tail && que_2[tail]<=a[i])80 tail--;81 que_2[++tail]=a[i];82 p2[tail]=i;83 }84 cout<<que_2[head]<<" ";85 for (i;i<=n;i++)86 {87 while(head<=tail && que_2[tail]<=a[i])88 tail--;89 que_2[++tail]=a[i];90 p2[tail]=i;91 while(p2[head]<=i-k)92 head++;93 cout<<que_2[head]<<" ";94 } 95 return 0;96 }
（完蛋了一直做傻逼题会不会rp--啊。。QAQ）
poj2823