无锡网站建设 君通科技,苏州网站建设书生,网站链接做二维码,网站如何优化关键词题目链接#xff1a;http://dsalgo.openjudge.cn/binarytree/12/ 总时间限制: 3000ms 内存限制: 65536kB描述给定m个数字序列#xff0c;每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列#xff0c;显然一共可以构造出n^m个新序列。接下来我们对每…题目链接http://dsalgo.openjudge.cn/binarytree/12/ 总时间限制: 3000ms 内存限制: 65536kB描述 给定m个数字序列每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和一共会得到n^m个和请找出最小的n个和 输入输入的第一行是一个整数T表示测试用例的数量接下来是T个测试用例的输入每个测试用例输入的第一行是两个正整数m0 m 100和n(0 n 2000)然后有m行每行有n个数数字之间用空格分开表示这m个序列序列中的数字不会大于10000输出对每组测试用例输出一行用空格隔开的数表示最小的n个和样例输入 1
2 3
1 2 3
2 2 3 样例输出 3 3 4 分析 这个题用优先队列来处理。维护一个长度为n的优先队列每次输入后都对前n个最小和进行更新m-1次迭代后得到最终的前n个最小和。 优先队列内部是用堆来实现的若是水平高的童鞋可以自己实现堆去试一下。 下面直接使用C STL的优先队列来完成工作。 关于优先队列可以参考https://www.cnblogs.com/huashanqingzhu/p/11040390.html 关于sort排序函数参考https://www.cnblogs.com/TX980502/p/8528840.html AC代码如下 1 #include cstdio2 #include iostream3 #include cstring4 #include queue5 #include algorithm6 using namespace std;7 8 const int maxn 2005;9 int t,m,n,a[maxn],b[maxn];
10 priority_queueint q;//利用a维护前n个最小和
11
12 int main()
13 {
14 scanf(%d,t);
15 while(t--) {
16 scanf(%d%d,m,n);
17 for (int i 0; i n; i) scanf(%d,a[i]);sort(a,an); //a存储前n个最小和
18 m--;
19 while(m--) {
20 for (int i 0; i n; i) scanf(%d,b[i]);sort(b,bn);
21 for (int i 0; i n; i) q.push(a[i]b[0]); //生成长度为n的优先队列
22 for (int i 1; i n; i) { //计算剩余的组合并更新队列
23 int j;
24 for (j 0; j n; j)
25 if(b[i]a[j]q.top()) q.pop(),q.push(b[i]a[j]);//a剪枝
26 else break;
27 if(j 0) break;//b剪枝b[i]a[0]都不行那b[i1]a[0]或b[i]a[1]也不行
28 }
29 for (int i n-1; i 0; i--) a[i] q.top(),q.pop(); //为下次更新作准备
30 }
31 for (int i 0; i n; i) printf(%d%c,a[i],i n-1?\n: );
32 }
33 return 0;
34 } View Code 代码来自csdnhttps://blog.csdn.net/xxiaobaib/article/details/78907588 转载于:https://www.cnblogs.com/huashanqingzhu/p/11040709.html
