首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#7318

Sequence 给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一…

Sequence

给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到n^m个和,请找出最小的n个和

时间限制:3000

内存限制:65536

输入

输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000

输出

对每组测试用例,输出一行用空格隔开的数,表示最小的n个和

样例输入

1
2 3
1 2 3
2 2 3

样例输出

3 3 4
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; priority_queue&lt;int&gt; que; int a[2005]; int b[2005]; // 用作中间数组 int main() {   int T;   cin &gt;&gt; T;   int m, n;   while (T--) {     cin &gt;&gt; m &gt;&gt; n;     for (int i = 0; i &lt; n; i++) {       scanf("%d", &amp;a[i]);     }     sort(a, a + n);             // 用a做总的和数组     for (int i = 1; i &lt; m; i++) // 轮接下来的序列     {       for (int j = 0; j &lt; n; j++) {         scanf("%d", &amp;b[j]);         que.push(a[0] + b[j]);       }       for (int j = 1; j &lt; n; j++) {         for (int k = 0; k &lt; n; k++) {           if (a[j] + b[k] &lt; que.top()) {             que.pop();             que.push(a[j] +                      b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数           }         }       }       for (int i = 0; i &lt; n; i++) {         a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序         que.pop();                // 队列已经被清空了,轮下一次       }     }     for (int i = 0; i &lt; n - 1; i++)       printf("%d ", a[i]);     printf("%d\n", a[n - 1]);   }   return 0; }</pre>
这道题暂未补解析。