HDU 1280第M大数スタックの応用

#include <iostream> #include<cstdlib> #include<cstdio> using namespace std; int N; int M; int sequence[3000]; int order[3000]; class Minheap { private: int* heap; int currentSize; int MaxHeapSize; void FilterDown(int start,int endOfheap) { int i=start; int j=2*i+1; int temp=heap[i]; while(j<=endOfheap) { if(j<endOfheap && heap[j]>heap[j+1])j++; if(temp<=heap[j])break; else {

                heap[i]=heap[j];

                i=j;

                j=2*j+1; } }

        heap[i]=temp; } void FilterUp(int start) { int j=start; int i=(start-1)>>1; int temp=heap[j]; while(i>=0) { if(heap[i]<=temp)break; else {

                heap[j]=heap[i];

                j=i;

                i=(i-1)>>1; } }

        heap[j]=temp; } public:

    Minheap() {

        currentSize=0; this->MaxHeapSize=M;

        heap=new int[M]; } void insert(int x) {

        heap[currentSize]=x;

        FilterUp(currentSize);

        currentSize++; } int top(){return heap[0];} int Remove() { int Min=heap[0];

        heap[0]=heap[currentSize-1];

        currentSize--;

        FilterDown(0,currentSize-1); return Min; } void modify(int x) {

        heap[0]=x;

        FilterDown(0,currentSize-1); } ~Minheap(){delete heap;} }; int main() { while(scanf("%d %d",&N,&M)!=EOF) { int i,j,k;

        Minheap * heap=new Minheap(); for(i=1;i<=M;i++) {

            heap->insert(0); } for(i=0;i<N;i++) {

            scanf("%d",&sequence[i]); } for(i=0;i<N;i++) { for(j=i+1;j<N;j++) { if((sequence[i]+sequence[j])>heap->top()) {

                    heap->modify(sequence[i]+sequence[j]); } } } for(i=M-1;i>=0;i--) {

            order[i]=heap->Remove(); } for(i=0;i<M-1;i++) {

            printf("%d ",order[i]); }

        printf("%d
",order[i]); } }