序列合并求前K小项 POJ2442

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 priority_queue<int>pq;
10 int an[3100];
11 int bn[3100];
12 
13 int main()
14 {
15     int T;
16     cin>>T;
17     while(T--)
18     {
19         int m,n;
20         scanf("%d%d",&m,&n);
21         for(int i=0;i<n;i++)
22             scanf("%d",&an[i]);
23         for(int i=1;i<m;i++)
24         {
25             for(int t=0;t<n;t++)
26             {
27                 scanf("%d",&bn[t]);
28             }
29             for(int t=0;t<n;t++)
30             {
31                 pq.push(an[0]+bn[t]);
32             }
33             for(int t=1;t<n;t++)
34             {
35                 for(int j=0;j<n;j++)
36                 {
37                     if(an[t]+bn[j]<pq.top())
38                     {
39                         pq.pop();
40                         pq.push(an[t]+bn[j]);
41                     }
42                 }
43             }
44             for(int t=0;t<n;t++)
45             {
46                 an[t]=pq.top();
47                 pq.pop();
48             }
49         }
50         cout<<an[n-1];
51         for(int i=n-2;i>=0;i--)
52             cout<<" "<<an[i];
53         cout<<endl;
54     }
55     return 0;
56 }

View Code

解题步骤：

1.将第一序列读入data1向量中，并按升序排序。

2.将数据读入data2向量中，并按升序排序。

将data2[0] + data1[i] ( 0<=i<=n-1)读入dataq向量中

用make_heap对dataq建堆。

然后data2[1] + data1[i] (0<=i<=n-1),如果data2[1] + data1[i]比堆dataq的顶点大,则退出，否则删除

堆的顶点，插入data2[1] + data1[i]。然后是data2[2],...data2[n - 1]

3.将dataq的数据拷贝到data1中，并对data1按升序排序

4.循环2,3步，直到所有数据读入完毕。

5.打印data1中的数据即为结果。

按此方法，每次只需和当前最小的K项中最大的那项比较就行，而不用比较n^m次