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

分组均衡性 在上机实验课上,老师将所有学生排列为 n 排,每排坐 m 个学生。每个学生有左右两个邻座(除了这一排的左右两端)。每个人可以和自己的邻座互相帮助完成…

分组均衡性

在上机实验课上,老师将所有学生排列为 n 排,每排坐 m 个学生。每个学生有左右两个邻座(除了这一排的左右两端)。每个人可以和自己的邻座互相帮助完成实验。除了每排左右两端的学生,中间的每个学生都可以同时与两个邻座分别协作。

由于每个学生的个人能力不同,假设协作产生的小组能力值是两个协作学生的能力值之和,老师希望知道,自己给出的座位安排在多大程度上是“均衡”的 —— 所谓分组均衡性,是指所有可能组成的协作小组的能力值的最大值与最小值之差。

给定一张座位安排表,请计算这个安排的分组均衡性。

时间限制:1000

内存限制:65536

输入

输入第一行给出 2 个正整数 n 和 m(2 ≤ n, m ≤ 100),依次为座位的排数和每排的人数。 随后 n 行,每行给出 m 个数字,代表对应座位上学生的能力值(为区间 [1, 100] 内的整数)。同行数字间以空格分隔。

输出

在一行中输出分组均衡性。


样例输入

3 5
10 80 30 95 60
79 55 63 84 41
98 23 72 85 58

样例输出

67

提示

样例解释:最强组合是第 3 排的 72+85=157;最弱组合是第 1 排的 10+80=90。因此两者之差为 67。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;bits/stdc++.h&gt; using namespace std; int main() { int n, m, a[110], b = 0, s = 1000000, bt, st, c; cin &gt;&gt; n &gt;&gt; m; for (int i = 1; i &lt;= n; i++) { for (int j = 0; j &lt; m; j++) { cin &gt;&gt; a[j]; } for (int j = 1; j &lt; m ; j++) { c = a[j] + a[j - 1]; if (c &gt; b) { b = c; } if (c &lt; s) { s = c; } } } cout &lt;&lt; b - s; return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;climits&gt; using namespace std; int main() { int n, m; cin &gt;&gt; n &gt;&gt; m; int max_sum = INT_MIN; int min_sum = INT_MAX; for (int i = 0; i &lt; n; ++i) { vector&lt;int&gt; row(m); for (int j = 0; j &lt; m; ++j) { cin &gt;&gt; row[j]; } // 计算当前行的所有相邻小组能力值 for (int j = 0; j &lt; m - 1; ++j) { int current_sum = row[j] + row[j + 1]; max_sum = max(max_sum, current_sum); min_sum = min(min_sum, current_sum); } } cout &lt;&lt; max_sum - min_sum &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。