| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 50738 | Accepted: 14590 | |
| Case Time Limit: 5000MS | ||
Description
| Window position | Minimum value | Maximum value |
|---|---|---|
| [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 |
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
Output
Sample Input
8 3 1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7
#include"cstdio" #include"cstring" #include"queue" #include"vector" using namespace std; const int MAXN=1000005; int a[MAXN]; int Min[MAXN]; int Max[MAXN]; int n,k; int cnt; struct comp1{ bool operator()(const int x,const int y) { return a[x] > a[y]; } }; struct comp2{ bool operator()(const int x,const int y) { return a[x] < a[y]; } }; priority_queue<int,vector<int>,comp1> que1; priority_queue<int,vector<int>,comp2> que2; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=k;i++) { que1.push(i); que2.push(i); } Min[cnt]=a[que1.top()]; Max[cnt]=a[que2.top()]; cnt++; for(int i=k+1;i<=n;i++) { que1.push(i); que2.push(i); while(i-que1.top()>=k) que1.pop();// 将窗口之外的删除 Min[cnt]=a[que1.top()]; while(i-que2.top()>=k) que2.pop(); Max[cnt]=a[que2.top()]; cnt++; } for(int i=0;i<cnt;i++) printf("%d%c",Min[i],(i==cnt-1)?‘\n‘:‘ ‘); for(int i=0;i<cnt;i++) printf("%d%c",Max[i],(i==cnt-1)?‘\n‘:‘ ‘); return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5185626.html