首页 > 代码库 > STL--F - Sequence(n*m->求最小的前m个和)
STL--F - Sequence(n*m->求最小的前m个和)
F - Sequence
Time Limit:6000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uDescription
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
做这个题首先思考两个问题
由这两个得出,要求n个数组每个数组m个值,数组1和数组2的和找出最小的m个,再用来和数组3求和,找到最小的m个,最终得到所有的数组中的最小的m个
由于每个数组都是有序的,而且我们要求的最小的m个,数组a[i][j]+队列中的值 > 队首的值,那么a[i][j]加上队列中以后的值都会大于队首,对于我们要求解的最小的m个值无意义。队列中保存了当前数组到之前所有数组的最小的m个和,不断更新队列
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; int a[110][2100] , b[2100] ; priority_queue <int> p ; int main() { int i , j , k , n , m , t ; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(i = 0 ; i < n ; i++) { for(j = 0 ; j < m ; j++) scanf("%d", &a[i][j]); sort(a[i],a[i]+m); } for(i = 0 ; i < m ; i++) p.push(a[0][i]) ; for(i = 1 ; i < n ; i++) { for(j = 0 ; j < m ; j++) { b[j] = p.top(); p.pop(); } for(j = 0 ; j < m ; j++) { for(k = m-1 ; k >= 0 ; k--) { if(j == 0) p.push( a[i][j]+b[k] ); else { if( a[i][j] + b[k] < p.top() ) { p.pop(); p.push(a[i][j]+b[k]); } else break; } } } } for(j = 0 ; j < m ; j++) { b[j] = p.top(); p.pop(); } for(j = m-1 ; j >= 0 ; j--) { if(j == 0) printf("%d\n", b[j]); else printf("%d ", b[j]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。