POJ2823 单调队列
此题用java解和C++解，差距足够足够大，如下图http://dl.iteye.com/upload/attachment/0072/2248/cd0724db-aed1-33be-ae7f-6c37a0347b88.jpg
原题http://poj.org/problem?id=2823
http://dl.iteye.com/upload/attachment/0072/2256/df389d64-57e2-3a24-867a-06bdc73bd13e.jpg
解题思路
这题还可以用单调队列进行求解。开两个队列，一个维护最大值，一个维护最小值。下面叙述最大队列，最小队列的方法类似。
最大队列保证队列中各个元素大小单调递减（注意，不是单调不上升），同时每个元素的下标单调递增。这样便保证队首元素最大，而且更新的时候队首永远是当前最大。因此，这个队列需要在两头都可以进行删除，在队尾插入。
维护方法：在每次插入的时候，先判断队尾元素，如果不比待插入元素大就删除，不断删除队尾直到队尾元素大于待插入元素或者队空。删除的时候，判断队首，如果队首元素下标小于当前段左边界就删除，不断删除队首直到队首元素下标大于等于当前段左边界（注意：这时队列肯定不为空），队首元素就是当前段的最优解。
#include<algorithm>using namespace std;int a;//数组数据int Q;//队列int I;//I表示队列中的Q在数组中的下标int OutMin;//最小值int OutMax;//最大值int n,k;void GetMin(){ int i; int head=1; int tail=0; for(i=1;i<k;++i) { while(head <=tail && Q>a) tail--; tail++; Q=a; I=i; } for(i=k;i<=n;++i) { while(head <=tail && Q>a) tail--; tail++; Q=a; I=i; while(I<=i-k) head++; OutMin = Q; }}void GetMax(){ int i; int head=1; int tail=0; for(i=1;i<k;++i) { while(head <=tail && Q<a) tail--; tail++; Q=a; I=i; } for(i=k;i<=n;++i) { while(head <=tail && Q<a) tail--; tail++; Q=a; I=i; while(I<=i-k) head++; OutMax=Q; }}int main(){ int i; scanf("%d%d",&n,&k); if(k>n) k=n; for(i=1;i<=n;++i) { scanf("%d",&a); } GetMin(); GetMax(); for(i=0;i<=(n-k);++i) { printf("%d%c", OutMin, (i < n - k) ? ' ' : '\n'); } for(i=0;i<=(n-k);++i) { printf("%d%c", OutMax, (i < n - k) ? ' ' : '\n'); } return 0;}
import java.util.Scanner;public class Main{Scanner scan=new Scanner(System.in);int n,k;int[] queue=new int;int[] Index=new int;int[] arr=new int;int[] MIN=new int;int[] MAX=new int;public static void main(String[] args){new Main().run();}void run(){n=scan.nextInt();k=scan.nextInt();if(k>n)k=n;for(int i=1;i<=n;i++){arr=scan.nextInt();}GetMin();GetMax();for(int i=0;i<=(n-k);i++){System.out.print(MIN+" ");}System.out.println();for(int i=0;i<=(n-k);i++){System.out.print(MAX+" ");}}void GetMin(){int head=1;int tail=0;for(int i=1;i<k;i++){while(head<=tail&&queue>arr)tail--;tail++;queue=arr;Index=i;}for(int i=k;i<=n;i++){while(head<=tail&&queue>arr)tail--;tail++;queue=arr;Index=i;while(Index<=i-k)head++;MIN=queue;}}void GetMax(){int head=1;int tail=0;for(int i=1;i<k;i++){while(head<=tail&&queue<arr)tail--;tail++;queue=arr;Index=i;}for(int i=k;i<=n;i++){while(head<=tail&&queue<arr)tail--;tail++;queue=arr;Index=i;while(Index<=i-k)head++;MAX=queue;}}}
页:
[1]