Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
g++换成C++便不超时了#include <iostream> #include <cstdio> using namespace std; const int MAX = 1000009; int arr[MAX]; int n,k; int v[MAX],id[MAX]; int min_queue[MAX]; int max_queue[MAX]; int front,rear; int main() { while(scanf("%d%d",&n,&k)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",&arr[i]); } front=rear=1; for(int i=1;i<k;i++) { while(front!=rear && v[rear-1]>arr[i]) rear--; v[rear]=arr[i]; id[rear++]=i; } for(int i=k;i<=n;i++) { while(front!=rear && v[rear-1]>arr[i]) rear--; v[rear]=arr[i]; id[rear++]=i; while(front!=rear && i-id[front]+1>k) front++; min_queue[i]=v[front]; } printf("%d",min_queue[k]); for(int i=k+1;i<=n;i++) printf(" %d",min_queue[i]); printf("\n"); front=rear=1; for(int i=1;i<k;i++) { while(front!=rear && v[rear-1]<arr[i]) rear--; v[rear]=arr[i]; id[rear++]=i; } for(int i=1;i<=n;i++) { while(front!=rear && v[rear-1]<arr[i]) rear--; v[rear]=arr[i]; id[rear++]=i; while(front!=rear && i-id[front]+1>k) front++; max_queue[i]=v[front]; } printf("%d",max_queue[k]); for(int i=k+1;i<=n;i++) printf(" %d",max_queue[i]); printf("\n"); } return 0; } ------------------------------------------------------------------- 写的好恶心啊,见谅,见谅。 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator