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

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

Sequence(2023.12)

给定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">// 参考答案1 #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><pre class="brush:cpp;toolbar:false">// 参考答案2 #include &lt;bits/stdc++.h&gt; using namespace std; typedef pair&lt;int, int&gt; pii; int m, n; vector&lt;int&gt; a[105]; struct Plan {   pii ptr;   bool last; // 记录本方案是否是由ptr2++得到的   int sum;   Plan() {}   Plan(int i, int j, pii _ptr, bool _last) {     ptr = _ptr;     last = _last;     sum = a[i][ptr.first] + a[j][ptr.second];   }   bool operator&lt;(const Plan &amp;oth) const { return sum &gt; oth.sum; } } init; priority_queue&lt;Plan&gt; Q; int main() {   int T;   cin &gt;&gt; T;   while (T--) {     scanf("%d%d", &amp;m, &amp;n);     for (int i = 1; i &lt;= m; i++) {       a[i].clear();       for (int j = 1, x; j &lt;= n; j++) {         scanf("%d", &amp;x);         a[i].push_back(x);       }       sort(a[i].begin(), a[i].end());     }     int i = 1;     for (int j = 2; j &lt;= m; j++, i ^= 1) {       init = Plan(i, j, make_pair(0, 0), 0);       while (!Q.empty())         Q.pop();       Q.push(init);       a[i ^ 1].clear();       while (!Q.empty()) {         Plan now = Q.top();         Q.pop();         a[i ^ 1].push_back(now.sum);         if (a[i ^ 1].size() &gt;= n)           break;         if (!now.last &amp;&amp; now.ptr.first &lt; n - 1)           Q.push(Plan(i, j, make_pair(now.ptr.first + 1, now.ptr.second), 0));         if (now.ptr.second &lt; n - 1)           Q.push(Plan(i, j, make_pair(now.ptr.first, now.ptr.second + 1), 1));       }     }     for (int k = 0; k &lt; a[i].size(); k++)       printf("%d ", a[i][k]);     printf("\n");   } }</pre>
这道题暂未补解析。