HDOJ 1280 앞 m 큰 수 (시간 최적화)

앞 m 큰 수
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13714    Accepted Submission(s): 4670
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
항 저 우 전기 ACM 합숙 훈련 대 훈련 경기 (VI)
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1425  1496  1029  1264  1236
물 문제 지만 시간 과 공간 이 끔찍 할 수 있 습 니 다. 어느 정도 배 운 후에 시간의 최적화 에 주의해 야 합 니 다. 514 MS, 19056 K, 530 B:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ni[3100],sum[5000000];
int main(){
    int n,m,i,j,k;
    while(~scanf("%d%d",&n,&m)){
        for(i=0;i<n;i++)
            scanf("%d",&ni[i]);
        k=0;
        memset(sum,0,sizeof(sum));
        for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
                sum[k++]=ni[i]+ni[j];//     
        sort(sum,sum+k);//     
        if(m>0) printf("%d",sum[k-1]);
        for(i=k-2;i>k-1-m;i--)
            printf(" %d",sum[i]);
        printf("
");
    }
    return 0;
}

0MS，1460K，633B：

#include<cstdio>
#include<cstring>
using namespace std;
int ni[3100],sum[10005];
int main(){
    int n,m,i,j;
    while(~scanf("%d%d",&n,&m)){
        for(i=0;i<n;i++)
            scanf("%d",&ni[i]);
        memset(sum,0,sizeof(sum));
        for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
                sum[ni[i]+ni[j]]++;    //     
        for(i=10000;i>=0;i--){
            while(sum[i]>0&&m>1){
                printf("%d ",i);
                sum[i]--; m--;
            }                   //     
            if(sum[i]>0&&m==1){
                printf("%d
",i);
                break;
            }                      //     
        }
    }
    return 0;
}