Pro. 1
给定k个有序表，取其中前n小的数字。组成一个新表，求该表？
算法：
由于 a1[1] < a1[2] < a1[3] ... <a1[n]
a2[1] < a2[2] < a2[3] ... < a2[n]
.........
ak[1] < ak[2]<ak[3]...... < ak[n]
首先每个有序表的第一个元素入堆，然后最小元素出堆。该元素入新表L，相应线性表的下一个元素入堆。
例如：如果出堆得是a2[2],那么a2[3]入堆。所以给每一个表增设一个标记。循环n次得到新表.
Pro. 2
给定两个长为n的有序表A,B，根据两表中任意两元素和得到一个大小为N^2的表，得到的新表的前n小的元素。（HDU上的一个。但是那个题目直接Hash做）
根据题意：
A[1] + B[1] < A[1] + B[2] .. < A[1] + B[n]
A[2] + B[1] < A[1] + B[2] .. < A[1] + B[n]
.......
A[n] + B[1] < A[1] + B[2] .. < A[1] + B[n]
这样就得到了n个有序表。 转化为pro 1 得到答案
Pro. 3
说到正题了。 给定m 个长为n 的有序表。 每个表取一个元素。得到m个元素。求和。 要求，求前n小的和。
每次考虑两个表， 根据 a[1][1 ...n] 与a[2][1...n] ，转化为pro.2 。求出一个大小为n的表 L
再考虑表Ｌ与a[3][1...n] 得到新的表L'
接着考虑a[4][1....n]
...... 最后得到的本题的答案
Sequence
|
Time Limit: 6000MS |
|
Memory Limit: 65536K |
|
Total Submissions: 6259 |
|
Accepted: 1953 |
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
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue>
using namespace std;
int t,n,m,A[2222],Q[2222];
struct node
{
int arr,id;
bool operator < (const node b) const
{
return arr>b.arr;
}
};
int matrix[2222][2222];
void fuuuuuc()
{
int cur=0;
int nowfrom[2222];
memset(nowfrom,0,sizeof(nowfrom));
priority_queue<node> q;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
matrix[i][j]=Q[i]+A[j];
if(j==0)
{
node x;
x.arr=matrix[i][0]; x.id=i;
q.push(x);
}
}
}
/*
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
*/
for(cur=0;cur<n;cur++)
{
node u=q.top(); q.pop();
// cout<<" -->: "<<u.id<<" "<<u.arr<<endl;
int ID=u.id;
Q[cur]=u.arr;
nowfrom[ID]++;
u.arr=matrix[ID][nowfrom[ID]];
q.push(u);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++)
{
scanf("%d",&Q[i]);
}
sort(Q,Q+n);
for(int i=1;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",A+j);
}
sort(A,A+n);
fuuuuuc();
}
for(int i=0;i<n;i++)
{
if(i) putchar(' ');
printf("%d",Q[i]);
}
putchar(10);
}
return 0;
}
|
* This source code was highlighted by YcdoiT. ( style: Codeblocks )