POJ 2442 Sequence

Sequence
Time Limit: 6000MS   Memory Limit: 65536K
Total Submissions: 5658   Accepted: 1722
Description
 
Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?
Input
 
The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.
Output
 
For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.
Sample Input
 
1
2 3
1 2 3
2 2 3
Sample Output
 
3 3 4
Source
 
POJ Monthly,Guang Lin
 
我手写了一个堆，却是tle，其实明白原理之后不用堆就可以。用堆还不是求最小值啊，直接找最小值就好了
[cpp]  
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
int a[2100],b[2100],heap[1000000],data[110][2100],Data[2100];  
int n,m,pos[10000];  
int cmp(const void *e,const void *f)  
{  
    return (*(int *)e-*(int *)f);  
}  
int main()  
{  
    void deal(int k);  
    int i,j,s,t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d %d",&m,&n);  
        for(i=1;i<=m;i++)  
        {  
            for(j=1;j<=n;j++)  
            {  
                scanf("%d",&Data[j-1]);  
            }  
            qsort(Data,n,sizeof(Data[0]),cmp);  
            for(j=1;j<=n;j++)  
            {  
                data[i][j]=Data[j-1];  
            }  
        }  
        for(i=1;i<=n;i++)  
        {  
            a[i-1]=data[1][i];  
        }  
        for(i=2;i<=m;i++)  
        {  
            deal(i);  
        }  
        for(i=0;i<=n-1;i++)  
        {  
            if(i==0)  
            {  
                printf("%d",a[i]);  
            }else  
            {  
                printf(" %d",a[i]);  
            }  
        }  
        printf("\n");  
    }  
    return 0;  
}  
void deal(int k)  
{  
    int i,j,min,key;  
    for(i=1;i<=n;i++)  
    {  
        pos[i]=0;  
    }  
    for(i=0;i<=n-1;i++)  
    {  
        b[i]=data[k][i+1];  
    }  
    for(i=1;i<=n;i++)  
    {  
        heap[i]=a[i-1]+b[0];  
    }  
    for(i=1;i<=n;i++)  
    {  
  
        for(j=1;j<=n;j++)  
        {  
            if(j==1)  
            {  
                min=heap[j]; key=j;  
            }else  
            {  
                if(heap[j]<min)  
                {  
                    min=heap[j]; key=j;  
                }  
            }  
        }  
        a[i-1]=heap[key];  
        heap[key]=heap[key]-b[pos[key]]+b[pos[key]+1];  
        pos[key]+=1;  
    }  
}

补充：软件开发 , C++ ,