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; } }
