首页 > 代码库 > POJ-2442 Sequence(手写堆优化)
POJ-2442 Sequence(手写堆优化)
Sequence
Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 9131 | Accepted: 3037 |
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
首先这题是可以用系统给的priority_queue的,不过毕竟现在我在学手写堆,于是就给自己找麻烦咯~
思路: 因为,要每行都取一个,构成一个和sum。需要找出n个sum。 我们需要一行一行的找,不妨先设前两行的最小的n个sum是由第一行n个数和第二行的第一个数构成的。 存入c[]数组里,然后一次遍历第二行其他的数,看是否有小于c[]数组里最大的数,然后替换,这是前两行的最小的n个sum已经找到,存到了c[]数组, 然后找前三行,同样设让第三行的第一个数与数组c[]所有的数加和, 然后遍历第三行其他的数,看是否有小于c[]数组里最大的数。替换。以此类推。找到第m-1行 结束寻找,这时数组c[]里就是题目要求的数组。
思路来源:http://www.tuicool.com/articles/VjuYFn
程序压了一点行,可能可读性会差一点
1 #include "bits/stdc++.h" 2 #define mem(a,b) memset(a,b,sizeof(a)) 3 #define F(z,x,y) for (z=x;z<=y;z++) 4 using namespace std; 5 typedef long long LL; 6 const int MAX=2005; 7 int cas; 8 int n,m; 9 int s[MAX],sum[MAX]; 10 struct Que{ 11 int h[MAX*100]; 12 int n; 13 Que (){ 14 mem(h,0); 15 n=0; 16 } 17 void heapify(int x){ 18 int child=x*2,key=h[x]; 19 while (child<=n){ 20 if (child<n && h[child]<h[child+1]) child++; 21 if (key<h[child]){h[x]=h[child];x=child,child=x*2;} 22 else break; 23 } 24 h[x]=key; 25 } 26 void insert(int key){ 27 int x=++n; 28 while (x>1){ 29 if (key>h[x/2]) h[x]=h[x/2],x/=2; 30 else break; 31 } 32 h[x]=key; 33 } 34 void del(){ 35 if (n==1) n=0; 36 else h[1]=h[n--],heapify(1); 37 } 38 }; 39 int main(){ 40 freopen ("sequence.in","r",stdin); 41 freopen ("sequence.out","w",stdout); 42 int i,j,k; 43 scanf("%d",&cas); 44 while (cas--){ 45 scanf("%d%d",&n,&m); 46 mem(s,0),mem(sum,0); 47 Que q; 48 F(i,1,m){ 49 scanf("%d",s+i); 50 } 51 F(i,2,n){ 52 F(j,1,m) 53 scanf("%d",sum+j); 54 F(j,1,m) 55 q.insert(sum[1]+s[j]); 56 F(j,2,m) 57 F(k,1,m){ 58 int mx=sum[j]+s[k]; 59 if (mx<q.h[1]){ 60 q.del(); 61 q.insert(mx); 62 } 63 } 64 F(j,1,m) 65 s[j]=q.h[j]; 66 mem(q.h,0); 67 q.n=0; 68 } 69 sort(s+1,s+m+1); 70 F(i,1,m){ 71 printf("%d ",s[i]); 72 } 73 printf("\n"); 74 } 75 return 0; 76 }
POJ-2442 Sequence(手写堆优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。