前m大的数

题目：

A - 前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

题解：

利用双重循环求输入数组两两相加的结果，利用sort函数实现从大到小排序，最后利用while(scanf("%d %d", &n, &m))类似语句实现多组输入即可。

代码实现：

#include <iostream> #include <algorithm> using namespace std; #define N 3010 /*定义宏定义常量的原因是它和常量一个性质，可以在定义数组时使用。数组定义时只能是常量或表达式。 （可以不要宏定义常量，把下面的N全部换成3010）*/ int beg[N],sum[N * N]; //因为main函数内存有限，比较大的数组最好都开在外面（数组可以开很大，至少3010*3010没问题） int main () { int m, n; while(scanf("%d %d", &n, &m) != EOF) /*EOF是一个计算机术语，为End Of File的缩写，在操作系统中表示资料源 无更多的资料可读取。此句表示读取数据结束后，终止循环。*/ { int i, j, k = 0; for( i = 0; i < n; i ++ ) scanf("%d",&beg[i]); for(int i = 0; i < n - 1; i ++ ) { for( j = i + 1; j < n; j ++ ) { sum[k] = beg[i] + beg[j]; k ++ ; } //实现两两相加 } sort(sum, sum + n * (n - 1) / 2, greater <int>()); for( i = 0; i < m; i ++ ) { printf("%d", sum[i]); if(i < m-1) printf(" "); } //最后一个数输出后不能输出空格，否则会发生格式错误 printf("\n"); } return 0; }