hdu 1280 用堆

我会带着你远行 2021-10-19 01:00 191阅读 0赞

# 前m大的数 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 2922    Accepted Submission(s): 1013**

Problem Description

还记得Gardon给小希布置的那个作业么？（上次比赛的1005）其实小希已经找回了原来的那张数表，现在她想确认一下她的答案是否正确，但是整个的答案是很庞大的表，小希只想让你把答案中最大的M个数告诉她就可以了。   
给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N\*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。

Input

输入可能包含多组数据，其中每组数据包括两行：   
第一行两个数N和M，   
第二行N个数，表示该序列。

Output

对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。

Sample Input

4 4 1 2 3 4 4 5 5 3 6 4

Sample Output

7 6 5 5 11 10 9 9 8

Author

Gardon

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    //#include<debug.h>
    const int inf=4498501;
    int M;
    struct node
    {
     int sum;
    }C[inf];
    int A[3000],B[3000];
    
    /*
    int cmp(const void *a,const void *b)
    {
        return (*(node *)a).sum < (*(node *)b).sum ? 1:-1;
    }
    */
    int swap(int &x,int &y)
    {
        int temp;
         temp=x;
         x=y;
         y=temp;
         return 0;
    }
    void down(int n,int i)
    {
       int flag=1;
       if((2*i)<=n)
       {  
          while(flag&& (i=2*i)<=n)
          {
          if(i+1<=n&&C[i+1].sum>C[i].sum)
          i++;
          if(C[i/2].sum<C[i].sum)
          {
          
          swap(C[i/2].sum,C[i].sum);
          
          }
          else 
          flag=0;
        
         } 
    }
      
    }    
    void makeheap(int n )
    {
      C[n].sum=C[0].sum;
      int i;
      for(i=n/2;i>=1;i--)
      down(n,i);
     // printf("**:%d\n",C[1]);
      
    } 
    
    void head_sort(int n)
    {
        int i;
        makeheap(n);
        for(i=n;i>=n-M+1;i--)
        {
         swap(C[1].sum,C[i].sum);
       
         down(i-1,1);
        
        }
    }   
        
      
    int main( )
    {
     int N;
     //Debug();
     while(scanf("%d%d",&N,&M)!=EOF)
     {
      int P,k=0;
     // P=N*(N-1)/2;
      
      int i,j;
      for(i=0;i<N;i++)
      {
       scanf("%d",&A[i]);
       //B[i]=A[i];
      }
      for(i=0;i<N;i++)
        for(j=i+1;j<N;j++)
        C[k++].sum=A[i]+A[j];
      
      
       head_sort(k);
       for(i=k;i>=k-M+1;i--)
       printf(i==k-M+1?"%d":"%d ",C[i].sum);
       printf("\n");
     }
     return 0;
    }

用堆写的，代码直的很长，我用qsort函数写时，超时了，悲剧，，，，。。估计是排序时，把所有

的都排了，等下再人优化下，用qsort写的。。也还可以用sort函数。。

转载于:https://www.cnblogs.com/tangcong/archive/2011/04/14/2016261.html