TZOJ 1242 求出前m大的数(预处理)

描述

给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=10000)并按从大到小的顺序排列。

输入

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

输出

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

样例输入

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

样例输出

7 6 5 5
11 10 9 9 8

题意

求出两两相加前m大的值

题解

先预处理一下，把每两个的和放入数组中

代码

#include<stdio.h>
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int a[3005],b[10001]={0},maxx=0;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                b[a[i]+a[j]]++;
                if(a[i]+a[j]>maxx)
                    maxx=a[i]+a[j];
            }
        }
        printf("%d",maxx);
        b[maxx]--;
        m--;
        int f=0;
        for(int i=maxx;i>=0;i--)
        {
            for(int j=b[i];j>0;j--)
            {
                if(m-->0)
                    printf(" %d",i);
                else
                {
                    f=1;break;
                }
            }
            if(f)break;
        }
        puts("");
    }
    return 0;
}