前m大的數
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17708 Accepted Submission(s): 6063
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
Author Gardon
Source
#include<iostream>
#include<string>
#include<sstream>
#include<set>
#include<algorithm>
using namespace std;
int c[4500000]={0};
int main()
{
int n,m;
while(cin>>n>>m)
{
int a[3001],i,j,k=0;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
c[k++]=a[i]+a[j];
}
sort(c,c+k);
for(i=k-1;i>k-1-m;i--)
{
if(i==(k-m))cout<<c[i]<<endl;
else cout<<c[i]<<" ";
}
}
}
//3000*3000=9000000/2=4500000;