poj 2823

---

原题

题意：

给定序列长度 n<106 ，窗口大小 k ，将窗口放到序列上，从左往右一格一格移动窗体，输出每个状态窗体中数字的最小值和最大值。

思路：

数据量为106， O(nlogn) 复杂度可过，也可以用单调队列，反正很裸。

单调队列：

于是我写了这么一个代码，g++交，T了……

#include<stdio.h> const int NMax=1000000; int n, k, temp, in[NMax+1]; int ans[NMax+1][2]; struct Queue{ int id[NMax+1]; int head, tail; void Init(){head=tail=0;} void DeleteTail(){tail--;} void Pop(){head++;} void Push(int i){id[tail++]=i;} bool Empty(){return head==tail;} int Head(){return id[head];} int Tail(){return id[tail-1];} }qMin, qMax; void PushDeal(int i){ //删除队尾条件判定：队列非空且队尾元素的值大于新加入元素的值 while(!qMin.Empty() && in[qMin.Tail()]>=in[i]) qMin.DeleteTail(); qMin.Push(i); while(!qMax.Empty() && in[qMax.Tail()]<=in[i]) qMax.DeleteTail(); qMax.Push(i); return; } int main(){ int i; scanf("%d%d", &n, &k); qMin.Init(); qMax.Init(); for(i=1; i<k; i++){ scanf("%d", in+i); PushDeal(i); } for(; i<=n; i++){ scanf("%d", in+i); PushDeal(i); //弹出队首条件判定：队列非空且队首元素的id与新加入元素的id相差等于窗口长度k while(!qMin.Empty() && qMin.Head() < i-k+1) qMin.Pop(); while(!qMax.Empty() && qMax.Head() < i-k+1) qMax.Pop(); ans[i][0]=in[qMin.Head()]; ans[i][1]=in[qMax.Head()]; } for(i=k; i<=n; i++) printf("%d%c", ans[i][0], i==n?'\n':' '); for(i=k; i<=n; i++) printf("%d%c", ans[i][1], i==n?'\n':' '); return 0; }

于是我试着把函数什么的都缩到main函数里，直接写成一团，中间又间或交了几次g++……又给我T了……

说好的单调队列裸题呢，翻别人代码……和我的也没什么差别啊，肿么一直T……

过了一会儿，想着用C++交一发，再不行写个整型的加速读入算了，于是……C++交A了。

Excuse me？

原来的代码 改后的代码 加了整型加速读入输出的情况和代码……

#include<stdio.h> #include<ctype.h> const int NMax=1000000; int n, k, temp, in[NMax+1]; int ans[NMax+1][2]; inline int ReadInt(){ char ch=getchar(); bool f=true; int num=0; while(!isdigit(ch)){ if(ch=='-') f = !f; ch=getchar(); } while(isdigit(ch)){ num=(num<<3)+(num<<1)+ch-'0'; ch=getchar(); } return f?num:-num; } void OutputInt(int num){ char out[20]; int top=0; if(num<0){ putchar('-'); num=-num; } do{ out[top++]=num%10+'0'; num/=10; }while(num); while(top--) putchar(out[top]); return; } struct Queue{ int id[NMax+1]; int head, tail; void Init(){head=tail=0;} void DeleteTail(){tail--;} void Pop(){head++;} void Push(int i){id[tail++]=i;} bool Empty(){return head==tail;} int Head(){return id[head];} int Tail(){return id[tail-1];} }qMin, qMax; void PushDeal(int i){ //删除队尾条件判定：队列非空且队尾元素的值大于新加入元素的值 while(!qMin.Empty() && in[qMin.Tail()]>=in[i]) qMin.DeleteTail(); qMin.Push(i); while(!qMax.Empty() && in[qMax.Tail()]<=in[i]) qMax.DeleteTail(); qMax.Push(i); return; } int main(){ int i; n=ReadInt(); k=ReadInt(); qMin.Init(); qMax.Init(); for(i=1; i<k; i++){ in[i]=ReadInt(); PushDeal(i); } for(; i<=n; i++){ in[i]=ReadInt(); PushDeal(i); //弹出队首条件判定：队列非空且队首元素的id与新加入元素的id相差等于窗口长度k while(!qMin.Empty() && qMin.Head() < i-k+1) qMin.Pop(); while(!qMax.Empty() && qMax.Head() < i-k+1) qMax.Pop(); ans[i][0]=in[qMin.Head()]; ans[i][1]=in[qMax.Head()]; } for(i=k; i<=n; i++){ OutputInt(ans[i][0]); putchar(i==n?'\n':' '); } for(i=k; i<=n; i++){ OutputInt(ans[i][1]); putchar(i==n?'\n':' '); } return 0; }

有毒的换成C++了，我无话可说，为了写个裸题容易么我……