题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1280
题目大意:
有N个数,让他们两两求和,得到 (n)*(n-1)/2 个数,让你输出前m大个数(从大到下)


给定一个包含N(N<=3000)个正整数的序列,每个数不超过5000,

思路:二重循环求出所有的和,加入multiset再输出就是,时间复杂度(n^2 * log(n^2))直接T。

我们可以看到,每个数<=5000,和的大小为<=10000, 那么我们可以对和进行桶排。时间复杂度O(n^2),哈希公式:A+B求和。

#include <bits/stdc++.h>

using namespace std;
const int maxn=5000006;

int Hx[10010];
int a[3005];
int main()
{
    int n, m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                Hx[a[i]+a[j]]++;
            }
        }
        for(int i=10000;i>=1;i--)
        {
            while(Hx[i]&&m)
            {
                printf("%d%c",i,(m==1?'\n':' '));
                Hx[i]--, m--;
            }
            if(m==0)
            {
                break;
            }
        }
    }

    return 0;
}