Poj2442 Sequence
给定M个长度为N的序列，从每个序列中任取一个数求和，可以构成 N^M 个和，求其中最小的N个和。
N≤2000,M≤100。
Input
第一行给出数据的组数
每组数据先给出M,N.(0 < m <= 100, 0 < n <= 2000).
接下来M行N列，描述这个数字矩形，每个数字<=10000
Output
如题
Sample Input
1
2 3
1 2 3
2 2 3
Sample Output
3 3 4
Sol1:
先简单想一下，如果数据只有一行的话，那很明显开一个小根堆，将元素值丢进去，再输出就好了。但问题是数据有多行，于是我们一行行处理。假设它只有两行，于是我们可以将第一行数据所在的小根堆中的元素一个个拿出来。然后让它加上第二行的每一行个数字，然后设计一个大根堆。为什么是大根堆呢，这里要想清楚。
因为我们的目的是求出其和最小的N个元素，设计成一个大根堆的话，如果当前堆顶元素+第二行某个元素的和小于大根堆的堆顶值，则说明这个堆顶值是没有必要存在的，要T掉。如果设计成一个小根堆的，则不能达到这个目的。于是我们维护一个只包含N个元素的大根堆。当上面的过程全处理结束后，再将大根堆的值倒入小根堆就好了。这样就得到了前两行的，符合题意的数值了。
接下来再一行行处理就好了。
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int n,m,a[4000005],b[4000005];
int main()
{
int t,flat,i,j,sum,k;
scanf("%d",&t);
while(t--)
{
int ai=1,bi=0,x,r,sum,a[2005];
scanf("%d%d",&n,&m);
priority_queue <int ,vector<int >,greater<int> >p;//小根堆
priority_queue <int ,vector<int >,less<int> >q;//大根堆
for(i=0; i<m; i++)
{
scanf("%d",&x);
p.push(x);
}
for(i=1; i<n; i++)
{
for(j=0; j<m; j++)
{
scanf("%d",&a[j]);
}
while(!p.empty()) //从小根堆中一个个取出数字
{
sum=p.top();
p.pop();
for(j=0;j<m;j++)//将sum与第i行的每个数字进行相加
{
if(q.size()==m&&q.top()>sum+a[j])
//控制大根堆中只有M个元素，且值尽可能的小
{
q.pop();
q.push(sum+a[j]);
}
else if(q.size()<m)
//如果大根堆的元素值没达到M个，就直接丢进去
{
q.push(sum+a[j]);
}
}
}
while(!q.empty())//将大根堆的元素值一个个丢到小根堆中
{
p.push(q.top());
q.pop();
}
}
flat=0;
for(i=0;i<m;i++)
{
if(flat)
{
printf(" ");
}
printf("%d",p.top());
p.pop();
flat=1;
}
printf("\n");
}
return 0;
}
//题后记
用这种方法来做有序表的求和那个题要跑20+s,但其实正常的方法10s是可以过的，因为这种方法常数太大了（对堆的各种操作太多了），正解可以看lyd书上。有个方法比这个难理解一点，但常数要小一些
Sol2:
下面这个做法非常好，利用数据的有序化，缩短时间
大致思路是:将第一行加到堆内，将第二行的数字升序排好。然后将堆中数字降序放到数组a中
将a数组的第一个数字加上第二行每个数字，结果放到一个堆中
拿出第二行的每个数字，假设为b,让b加上a数组中每个数字
（一定是倒过来加，保证加出来的数字越来越大,如果加出来的数字比大根堆的堆顶小就代替之，否则说是加不下去了直接break;
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
priority_queue<int>que;
int m,n;
int num[1111][2222];
int a[2222];
int main()
{
#ifndef ONLINE_JUDGE
freopen("G:/1.txt","r",stdin);
freopen("G:/2.txt","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&num[i][j]);
}
}
for(int i=1;i<=n;i++) //将第一行的数字压入堆
{
que.push(num[1][i]);
}
for(int i=2;i<=m;i++) //从第二行到最后一行
{
sort(num[i]+1,num[i]+1+n);
//升序排好 ?为什么呢?因为我们是要尽量取小值，所以控制最先入堆的数字值尽可能小一点
//后面再找出来的数字，如果大于它就直接break了.不错不错
for(int j=1;j<=n;j++)
//将堆中的数字放到数组,数组中的值是从大到小的,弹完后注意堆为空了
{
a[j]=que.top();
que.pop();
}
for(int j=1;j<=n;j++)
//将堆中数字加上当前行的第一个数字，这样的结果明显是符合题意的
{
que.push(num[i][1]+a[j]);
}
for(int j=2;j<=n;j++) //当前行的第二个数字到最后一个数字
{
for(int k=n;k>=1;k--)
// 与a数组的数字一个个加，注意这是个逆循环，也就是说所加的a[k]的值会越来越大
if(num[i][j]+a[k]<que.top())
{
que.pop();
que.push(num[i][j]+a[k]);
}
else //没有必要加下去了,因为后面要加的a[k]的值越来越大了
{
break;
}
}
}
for(int i=1;i<=n;i++)
{
a[i]=que.top();
que.pop();
}
for(int i=n;i>=2;i--)
{
printf("%d ",a[i]);
}
printf("%d\n",a[1]);
}
}
原文：https://www.cnblogs.com/cutemush/p/11679069.html