OI——前m大的数

封面女神:Selena Gomez,美国演员,歌手,扮演迪士尼公主出道,代表作:《Same Old Love》


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

Answer

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10010;
int a[maxn],b[3060];
int n,m,len = sizeof (a);
int main(){
	while (scanf ("%d%d",&n,&m) != EOF)
	{
		int flag = 1;
		memset (a,0,len);
		for (int i = 0; i < n; i++){
			scanf ("%d",&b[i]);
		}
		for (int i = 0; i < n - 1; i++){
			a[b[i] + b[j]]++;
		}
		for (int i = maxn; i >= 0; i--){
			while (a[i]){
				a[i]--;
				if (--m){
					printf ("%d ",i);
				}
				else {
					printf ("%d\n",i);
					flag = 0;
					break;
				}
			}
			if (!flag){
				break;
			}
		}
	}
	return 0;
}

Explanation

这道题钢哥说是哈希,然而实际上这丫的就是个桶排序。

进行加和的时候,直接在这个值所在的的数组的位置加一,最后从后往前查,并一边累加一边输出,直到正好到m,输出后break


欢迎打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注