Sequence

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 1 /* 2 解题步骤： 3 1，输入第一个序列并进行升序排序 4 2，输入一个序列进行升序排序，并将num1[0]+num2[i](0<=i<=n-1)结果放入优先队列 5 que中，然后num1[1]+num2[i](0<=i<=n-1)，若num1[1]+num2[i](0<=i<=n-1)>que.top() 6 就删除que的队首并将num1[1]+num2[i](0<=i<=n-1)进队列，然后是num1[2]+num2[i](0<=i<=n-1)... 7 3, 将que中的元素拷贝到num1[]中，注意是升序排列 8 4，循环2,3直到所有数据读入完毕 9 5，打印num1[]中数据 10 */ 11 #include<stdio.h> 12 #include<stdlib.h> 13 #include<algorithm> 14 #include<queue> 15 #include<iostream> 16 using namespace std; 17 18 int num1[2001],num2[2001]; 19 int main() 20 { 21 int t,n,m; 22 scanf("%d",&t); 23 while(t--) 24 { 25 priority_queue< int, deque<int>, less<int> >que; 26 while(!que.empty()) 27 que.pop(); 28 scanf("%d %d",&m,&n); 29 for(int j = 0; j < n; j++) 30 scanf("%d",&num1[j]); 31 sort(num1,num1+n); 32 33 for(int i = 1; i < m; i++)//再输入m-1个序列，也相当于进行m-1次两个序列的归并 34 { 35 for(int j = 0; j < n; j++) 36 { 37 scanf("%d",&num2[j]); 38 que.push(num2[j] + num1[0]); 39 } 40 sort(num2,num2+n); 41 for(int k = 1; k < n; k++) 42 for(int l = 0; l < n; l++) 43 { 44 if(num1[k] + num2[l] > que.top()) 45 break; 46 47 que.pop(); 48 que.push(num1[k]+num2[l]); 49 50 } 51 for(int j = 0; j < n; j++) 52 { 53 num1[n-1-j] = que.top(); 54 que.pop(); 55 } 56 } 57 printf("%d",num1[0]); 58 for(int j = 1; j < n; j++) 59 printf(" %d",num1[j]); 60 printf("\n"); 61 } 62 return 0; 63 } View Code

priority_queue：优先队列

顾名思义，这个东西可以用于存放单调的数据，后面将会看到用于优化Dijkstra

有3个类函数：

void push(元素类型   变量)

void pop()

int top()

int size()

bool empty()

分别是：

加入类型是XXX的变量XXX弹出队列首元素取优先队列的队首元素的值返回队列元素数量查看队列是否为空

定义：

priority_queue <数据类型，容器类型，元素比较方式>priority_queue <数据类型，容器类型>priority_queue <数据类型>

数据类型：int,double.....

容器类型：vector（默认），deque，但不能是list

元素比较方式：less（默认，不上升序），greater（不下降序）;

 

优先队列的第一种用法，也是最常用的用法：

 

priority_queue< int> qi;

 

通过<操作符可知在整数中元素大的优先级高。故示例1中输出结果为：9 6 5 3 2第二种方法：在示例1中，如果我们要把元素从小到大输出怎么办呢？这时我们可以传入一个比较函数，使用functional.h函数对象作为比较函数。

 

priority_queue< int, vector< int>, greater< int> >qi2;

 

其中第二个参数为容器类型。第二个参数为比较函数。故示例2中输出结果为：2 3 5 6 9第三种方法：自定义优先级。

 

struct node{    friend bool operator< (node n1, node n2)    {        return n1.priority < n2.priority;    }    int priority;    int value;};

 

在该结构中，value为值，priority为优先级。通过自定义operator<操作符来比较元素中的优先级。在示例3中输出结果为：优先级  值9          58          26          12          31          4但如果结构定义如下：

 

struct node {      friend bool operator> (node n1, node n2)     {          return n1.priority > n2.priority;     }      int priority;      int value; };

则会编译不过（G++编译器）因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。而且自定义类型的<操作符与>操作符并无直接联系，故会编译不过。

补充的一点是：

我们可以自己写一个比较类，还设定优先级：

struct cmp{    bool operator() (const int &a, const int &b)    {        return dist[a] > dist[b];    }};

priority_queue<int,vector<int>,cmp> q;(按照元素的dist大小从小到大排序).

 

转载于:https://www.cnblogs.com/LK1994/p/3225167.html

相关资源：JAVA上百实例源码以及开源项目