[堆排序]poj 2823：Sliding Window

 

大致题意：

    给出一列共n个数，和一个正整数k。对于所有的大于等于1，小于等于n-k的数i，求出在[i,i+k]这个区间中最大的数和最小的数  

大致思路：    

    借鉴 依然 的思路，要了解堆排序的大致运转方式以及堆内元素之间的调整过程。

 

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000050;
int num[nMax],heap[nMax];
int n,heapsize;
int pos[nMax];   //表示数组第i个元素在堆内的位置。
int id[nMax];    //堆内第i个元素对应的数组下标.
int leftson(int a){return a<<1;}
int rightson(int a){return (a<<1)+1;}
int parent(int a){return a>>1;}
void exchange(int a,int b){   //交换堆内a位置和b位置的元素
    int tmp;
    tmp=pos[id[a]],pos[id[a]]=pos[id[b]],pos[id[b]]=tmp;
    //swap(pos[id[a]],pos[id[b]]);
    tmp=id[a],id[a]=id[b],id[b]=tmp;
    tmp=heap[a],heap[a]=heap[b],heap[b]=tmp;
}

void minheap(int loc){      //以loc向下调整，为loc找到正确的位置，建立小根堆~~
    int tmp=loc,l=leftson(loc),r=rightson(loc);
    if(l<=heapsize&&heap[l]<heap[tmp])tmp=l;
    if(r<=heapsize&&heap[r]<heap[tmp])tmp=r;
    if(loc!=tmp){
        exchange(loc,tmp);
        minheap(tmp);
    }
}

void maxheap(int loc){      ////以loc向下调整，为loc找到正确的位置，建立大根堆~~
    int tmp=loc,l=leftson(loc),r=rightson(loc);
    if(l<=heapsize&&heap[l]>heap[tmp])tmp=l;
    if(r<=heapsize&&heap[r]>heap[tmp])tmp=r;
    if(loc!=tmp){
        exchange(loc,tmp);
        maxheap(tmp);
    }
}

void build(int f,int len){   //f=0时求小根堆，否则求大根堆   len:堆的大小
    int i;
    if(!f){
        for(i=len/2;i>0;i--){
            minheap(i);
        }
    }
    else{
        for( i=len/2;i>0;i--){
            maxheap(i);
        }
    }
}

void adjmin(int a){         //分别向下和向上找到堆中a位置元素应该在的位置
    minheap(a);
    while(a>1&&heap[parent(a)]>heap[a]){
        exchange(a,parent(a));
        a=parent(a);
    }
}

void adjmax(int a){
    maxheap(a);
    while(a>1&&heap[parent(a)]<heap[a]){
        exchange(a,parent(a));
        a=parent(a);
    }
}

int main(){
    int i,j,p;
    scanf("%d%d",&n,&heapsize);
    for(i=1;i<=n;i++){
        scanf("%d",&num[i]);
        heap[i]=num[i];
        pos[i]=id[i]=i;
    }
    build(0,heapsize);
    printf("%d ",heap[1]);
    for(i=heapsize+1;i<=n;i++){
        p=pos[i-heapsize];
        exchange(i, p);
        adjmin(p);
        printf("%d ",heap[1]);
    }printf("\n");
///////////////////////////   下面来求区间最大值
    for(i = 1;i<=n;i++){
        pos[i]=id[i]=i;
        heap[i]=num[i];
    }
    build(1,heapsize);
    printf("%d ",heap[1]);
    for(i=heapsize+1;i<=n;i++){
        p=pos[i-heapsize];
        exchange(i, p);
        adjmax(p);
        printf("%d ",heap[1]);
    }printf("\n");
    return 0;
}

评论

2 楼 暴风雪 2012-01-27  

f12345 写道

这是一道经典的单调优化dp

主要是想自己实现一遍对排序啊，以前只在数据结构书上看到过的~~

1 楼 f12345 2012-01-26  

这是一道经典的单调优化dp