HDU 1280 前m大的数

http://acm.hdu.edu.cn/showproblem.php?pid=1280

hash+最大堆，STL堆

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int hash[10001];
int main()
{
    int n,m;
    priority_queue <int> q;
    while(~scanf("%d%d",&n,&m))
    {
        int a[3001];
        memset(hash,0,sizeof(hash));
        for(int i=0;i<n;i++)
            scanf("%d",a+i);
        int cnt=0;
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++)
                hash[a[i]+a[j]]++;
        for(int i=1;i<10001;i++)
            if(hash[i])
                while(hash[i])
                {
                    q.push(i);
                    hash[i]--;
                }
        int flag=1;
        while(m--)
        {
            if(flag)
            {
                printf("%d",q.top());
                flag=0;
            }
            else
                printf(" %d",q.top());
            q.pop();
        }
        putchar('\n');
        while(!q.empty())
            q.pop();
    }
    return 0;
} 

 手写堆

#include <iostream>
#include <queue>
#include <algorithm>
#include <malloc.h>
using namespace std;
int heapsize,*heap ;
void up(int x)//自下而上调整堆 
{
    while(x!=1)
    {
        if(heap[x>>1]<heap[x])//
        {
            swap(heap[x>>1],heap[x]) ;
            x>>=1 ;
        }
        else 
            break ;
    }
} 
void down(int x)//自上而下调整堆 
{
    int y=x<<1 ;
    while(y<=heapsize)
    {
        if(y<heapsize && heap[y]<heap[y+1])
            y++ ;
        if(heap[y]>heap[x])
        {
            swap(heap[y],heap[x]) ;
            x=y,y=x<<1 ;
        }    
        else
            break ;
    }
}
void pop()//取出堆顶元素 
{
    heap[1]=heap[heapsize--] ;
    down(1) ;
}
void push(int x)//增加新元素
{
    heap[++heapsize]=x ;
    up(heapsize) ;
}
int hash[10001];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int a[3001];
        heap=(int*)malloc(1500*2999*4) ;
        memset(hash,0,sizeof(hash));
        for(int i=0;i<n;i++)
            scanf("%d",a+i);
        int cnt=0;
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++)
                hash[a[i]+a[j]]++;
        for(int i=1;i<10001;i++)
            if(hash[i])
                while(hash[i])
                {
                    push(i);
                    hash[i]--;
                }
        int flag=1;
        while(m--)
        {
            if(flag)
            {
                printf("%d",heap[1]);
                flag=0;
            }
            else
                printf(" %d",heap[1]);
            pop() ;
        }
        putchar('\n');
        free(heap) ;
    }
    return 0;
}