HDUOJ 1280 前m大的数 (hash)

Problem Description
给定一个包含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

solution:这个题还是hash呀，用暴力排序铁定超时，用hash数组保存每个和的个数，倒着输出一遍就OK了，用一个hash比暴力排序都简单，掌握方法。

#include <bits/stdc++.h>
using namespace std;

int arr[3001], cnt[10001];
bool flag = false;//输出空格判定

int main()
{
	int n, m;
	while (cin >> n >> m)
	{
		fill(cnt, cnt + 10001, 0);
		for (int i = 0; i < n; ++i)scanf("%d", &arr[i]);
		for (int i = 0; i < n; ++i)
		{
			for (int j = i + 1; j < n; ++j)++cnt[arr[i] + arr[j]];
		}
		flag = false;
		for (int i = 10000; i > 0 && m > 0; --i)
		{
			while (cnt[i] && m){
				if (flag)putchar(' ');
				flag = true;
				printf("%d", i);
				--cnt[i];
				--m; 
			}
		}
		putchar('\n');
	}
	return 0;
 }