Sequence
| Time Limit: 6000MS |
|
Memory Limit: 65536K |
| Total Submissions: 7011 |
|
Accepted: 2262 |
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
解题思路：
有m行，每行n个数，从每行中取出一个数相加一起求出sum，这样的sum有n的m次方个。要求的前n个最小的sum值。
第一次使用STL里面的堆，一开始对pop_heap()有点不太理解，后来明白了，比如对数组heap[n]，最大下标为n-1建堆，默认的是建立大顶堆，heap[0]是数组中最大的数，写一条pop_heap()语句，就是把heap[0]和 heap[n-1]互换，然后重新对 heap[0]到heap[n-2] （除去最后一个元素）重新建堆，heap[0]依然是最大值，这样相当于更新最大值的操作。
对于本题，堆的性质可以很好的运用。 三个数组old[n] , new [n] , heap[n]，old[]是用来保存前i行元素每行取出一个元素加起来所得的前n个最小sum，new[n]是第i+1行的输入元素，heap[n]是中间数组，用来建堆，并更新其最大值元素，每处理完第i行，获得前i行的前n个最小sum（这时保存在heap[]里面），就把heap[]元素赋给old[]，这样前m行都处理完毕后，再对old[]数组从小到大排一次序，输出即为所求了。
下面具体说一下heap[]的作用。
一开始把第一行的元素赋给old[], 并对其排序，然后将第一行的元素都加上第二行排序后的第一个元素，把n个值放到heap[]里面，这样就获得了一个临时的前两行的前n个sum值，但这并不一定是前两行最小的前n个sum值 ，因为第二行也有n个元素，得枚举出所有情况（即第二行的第二个，第三个...元素分别与第一行的所有值相加获得sum值）要在这些所有的情况里面取最小的前n个，这就要发挥堆的作用了，前面说临时的前n个sum值保存在heap[]里面了，然后对heap[]进行建堆make_heap(heap,heap+n);默认大顶堆，即heap[0]是最大值，在枚举的时候如果有发现求出的一个临时sum值（temp)比heap[ 0 ]要小，那就需要对heap[0]更新，因为我们是要求前n个最小的sum值，用 pop_heap(heap,heap+n);把最大值heap[0]与heap[n-1]互换，然后另heap[n-1] = temp；这样heap[]最大值就更新了（原来的最大值从数组中去除），但不知道是数组中的哪一个值，push_heap(heap,heap+n); 对其重新建堆，这样heap里面的最大的就是heap[0] 了。枚举完，更新完就把前两行的前n个最小的sum值求出来了，剩下的行是相同的操作。 上面的排序是为了减少不必要的操作，在枚举时可以提前退出，这就和 排序好的 2,4,5,6我们要最小的值，那就取2，不用考虑后面的数了一样。
代码：
#include
#include
using namespace std; const int maxn=2010; int Old[maxn],New[maxn],heap[maxn]; int main() { int t;cin>>t; int m,n; while(t--) { cin>>m>>n; for(int i=0;i
>Old[i]; sort(Old,Old+n); m--; while(m--) { for(int i=0;i
>New[i]; sort(New,New+n); for(int i=0;i
下面贴一下堆的知识：http://blog.csdn.net/hnust_xiehonghao/article/details/9172875转载
最大堆最小堆代码实现
http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621
最大堆 最小堆原理图
http://www.cnblogs.com/wu8685/archive/2010/12/30/1922218.html
STL 的堆操作
http://hi.baidu.com/solofancy/item/14acd02b9743f7d30f37f927
http://blog.csdn.net/morewindows/article/details/6967409
STL 的堆操作 来自上面的博客
STL里面的堆操作一般用到的只有4个:make_heap();、pop_heap();、push_heap();、sort_heap();
他们的头文件函数是#include
首先是make_heap();
他的函数原型是：void make_heap(first_pointer,end_pointer,compare_function);
一个参数是数组或向量的头指针，第二个向量是尾指针。第三个参数是比较函数的名字。在缺省的时候，默认是大跟堆。（下面的参数都一样就不解释了）
作用：把这一段的数组或向量做成一个堆的结构。范围是(first,last)
然后是pop_heap();
它的函数原型是：void pop_heap(first_pointer,end_pointer,compare_function);
作用：pop_heap()不是真的把最大（最小）的元素从堆中弹出来。而是重新排序堆。它
把first和last交换，然后将[first,last-1)的数据再做成一个堆。
接着是push_heap() void pushheap(first_pointer,end_pointer,compare_function);
作用：push_heap()假设由[first,last-1)是一个有效的堆，然后，再把堆中的新元素加
进来，做成一个堆。
最后是sort_heap()void sort_heap(first_p