此题用java解和C++解,差距足够足够大,如下图
原题
http://poj.org/problem?id=2823
解题思路
这题还可以用单调队列进行求解。开两个队列,一个维护最大值,一个维护最小值。下面叙述最大队列,最小队列的方法类似。
最大队列保证队列中各个元素大小单调递减(注意,不是单调不上升),同时每个元素的下标单调递增。这样便保证队首元素最大,而且更新的时候队首永远是当前最大。因此,这个队列需要在两头都可以进行删除,在队尾插入。
维护方法:
在每次插入的时候,先判断队尾元素,如果不比待插入元素大就删除,不断删除队尾直到队尾元素大于待插入元素或者队空。删除的时候,判断队首,如果队首元素下标小于当前段左边界就删除,不断删除队首直到队首元素下标大于等于当前段左边界(注意:这时队列肯定不为空),队首元素就是当前段的最优解。
#include<algorithm>
using namespace std;
int a[1000011];//数组数据
int Q[1000011];//队列
int I[1000011];//I[i]表示队列中的Q[i]在数组中的下标
int OutMin[1000011];//最小值
int OutMax[1000011];//最大值
int n,k;
void GetMin()
{
int i;
int head=1;
int tail=0;
for(i=1;i<k;++i)
{
while(head <=tail && Q[tail]>a[i])
tail--;
tail++;
Q[tail]=a[i];
I[tail]=i;
}
for(i=k;i<=n;++i)
{
while(head <=tail && Q[tail]>a[i])
tail--;
tail++;
Q[tail]=a[i];
I[tail]=i;
while(I[head]<=i-k)
head++;
OutMin[i-k] = Q[head];
}
}
void GetMax()
{
int i;
int head=1;
int tail=0;
for(i=1;i<k;++i)
{
while(head <=tail && Q[tail]<a[i])
tail--;
tail++;
Q[tail]=a[i];
I[tail]=i;
}
for(i=k;i<=n;++i)
{
while(head <=tail && Q[tail]<a[i])
tail--;
tail++;
Q[tail]=a[i];
I[tail]=i;
while(I[head]<=i-k)
head++;
OutMax[i-k]=Q[head];
}
}
int main()
{
int i;
scanf("%d%d",&n,&k);
if(k>n)
k=n;
for(i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
GetMin();
GetMax();
for(i=0;i<=(n-k);++i)
{
printf("%d%c", OutMin[i], (i < n - k) ? ' ' : '\n');
}
for(i=0;i<=(n-k);++i)
{
printf("%d%c", OutMax[i], (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[1000005];
int[] Index=new int[1000005];
int[] arr=new int[1000005];
int[] MIN=new int[1000005];
int[] MAX=new int[1000005];
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[i]=scan.nextInt();
}
GetMin();
GetMax();
for(int i=0;i<=(n-k);i++)
{
System.out.print(MIN[i]+" ");
}
System.out.println();
for(int i=0;i<=(n-k);i++)
{
System.out.print(MAX[i]+" ");
}
}
void GetMin(){
int head=1;
int tail=0;
for(int i=1;i<k;i++)
{
while(head<=tail&&queue[tail]>arr[i])
tail--;
tail++;
queue[tail]=arr[i];
Index[tail]=i;
}
for(int i=k;i<=n;i++)
{
while(head<=tail&&queue[tail]>arr[i])
tail--;
tail++;
queue[tail]=arr[i];
Index[tail]=i;
while(Index[head]<=i-k)
head++;
MIN[i-k]=queue[head];
}
}
void GetMax(){
int head=1;
int tail=0;
for(int i=1;i<k;i++)
{
while(head<=tail&&queue[tail]<arr[i])
tail--;
tail++;
queue[tail]=arr[i];
Index[tail]=i;
}
for(int i=k;i<=n;i++)
{
while(head<=tail&&queue[tail]<arr[i])
tail--;
tail++;
queue[tail]=arr[i];
Index[tail]=i;
while(Index[head]<=i-k)
head++;
MAX[i-k]=queue[head];
}
}
}
- 大小: 12.8 KB
- 大小: 25.4 KB
分享到:
相关推荐
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
我的博客链接:http://blog.csdn.net/CABI_ZGX
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
模拟题 要注意时间的处理 使用优先队列处理请求的事件 进行适当的运算符重载,可以简化代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码