简答题
偏难
#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 <bits/stdc++.h>
using namespace std;
int main() {
int n, m, a[110], b = 0, s = 1000000, bt, st, c;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[j];
}
for (int j = 1; j < m ; j++) {
c = a[j] + a[j - 1];
if (c > b) {
b = c;
}
if (c < s) {
s = c;
}
}
}
cout << b - s;
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int max_sum = INT_MIN;
int min_sum = INT_MAX;
for (int i = 0; i < n; ++i) {
vector<int> row(m);
for (int j = 0; j < m; ++j) {
cin >> row[j];
}
// 计算当前行的所有相邻小组能力值
for (int j = 0; j < 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 << max_sum - min_sum << endl;
return 0;
}</pre>
这道题暂未补解析。