Posted on 2010-04-08 21:03
Initiate 阅读(562)
评论(0) 编辑 收藏 引用 所属分类:
数据结构
方法：建两个堆，同时维护一个大根堆和一个小根堆
用一对指针就行卡位
弹出的时候如果在这个区间就记录下来，如果不在区间内就扔掉。
#include<iostream>
using namespace std;
int a[1000010];
int minout[1000010],maxout[1000010];
int n,k;
struct node{
int key;
int pla;
};
struct heap//堆
{
int size;
struct node elem[2000010];
}minh,maxh;
void insertmin(int x,int p)
{
int i= ++minh.size;
while(minh.elem[i/2].key > x)
{
minh.elem[i]=minh.elem[i/2];
i /=2;
}
minh.elem[i].key=x;
minh.elem[i].pla=p;
}
void deletemin()
{
int i,child,last,place;
last=minh.elem[minh.size].key;
place=minh.elem[minh.size].pla;
minh.size--;
for(i=1;i*2 <= minh.size;i = child)
{
child=2*i;
if(child != minh.size && minh.elem[child+1].key < minh.elem[child].key )
child++;
if( last > minh.elem[child].key )
minh.elem[i] = minh.elem[child];
else break;
}
minh.elem[i].key=last;
minh.elem[i].pla=place;
}
void insertmax(int x,int p)
{
int i= ++maxh.size;
while(maxh.elem[i/2].key < x)
{
maxh.elem[i]=maxh.elem[i/2];
i /=2;
}
maxh.elem[i].key=x;
maxh.elem[i].pla=p;
}
void deletemax()
{
int i,child,last,place;
last=maxh.elem[maxh.size].key;
place=maxh.elem[maxh.size].pla;
maxh.size--;
for(i=1;i*2 <= maxh.size;i = child)
{
child=2*i;
if(child != maxh.size && maxh.elem[child+1].key > maxh.elem[child].key )//
child++;
if( last < maxh.elem[child].key )//
maxh.elem[i] = maxh.elem[child];
else break;
}
maxh.elem[i].key=last;
maxh.elem[i].pla=place;
}
void cal()
{
int i;
minh.size=0;
minh.elem[0].key=-INT_MAX;
maxh.size=0;
maxh.elem[0].key=INT_MAX;
for(i=1;i<=k;i++)
{
insertmin(a[i],i);
insertmax(a[i],i);
}
int p1=1,p2=k;
while(p2<=n)
{
while(minh.elem[1].pla < p1 || minh.elem[1].pla>p2)
deletemin();
while(maxh.elem[1].pla < p1 || maxh.elem[1].pla>p2)
deletemax();
minout[p1]=minh.elem[1].key;
maxout[p1]=maxh.elem[1].key;
p1++;
p2++;
insertmin(a[p2],p2);
insertmax(a[p2],p2);
}
}
int main()
{
int i;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
cal();
for(i=1;i<=n-k;i++)
printf("%d ",minout[i]);
printf("%d\n",minout[n-k+1]);
for(i=1;i<=n-k;i++)
printf("%d ",maxout[i]);
printf("%d\n",maxout[n-k+1]);
}