专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
一、题目描述
1到n的n个连续的数字组成一个数组，n为3的倍数
每次按照顺序从数组中取出3个元素，去掉这3个元素中的一个最大值和一个最小值，并将剩下的元素累加为S，S初始值为0
可以通过调整数组中元素的位置改变最终结果，每移动一个元素计为移动一次。
请计算最少移动几次可以使得数组和S最大。
二、输入描述
数组长度n的范围为[3, 600]
数组中数字范围[1, 10000]
数组由一个字符串表示，不同数字元素之间使用空格分隔
三、输出描述
移动次数是一个自然数
无需移动，返回0
四、测试用例
测试用例1
1、输入
3 8 9 7 4 2 5 6 1
2、输出
1
3、说明
需要一次交换操作（例如，将T0中的一个Cat 2元素与T2中的一个Cat 1元素交换）来平衡所有三元组的类别。
测试用例2
1、输入
1 2 3 4 5 6 7 8 9
2、输出
3
3、说明
T0需要给出2个Cat 0，T1需要给出2个Cat 1，T2需要给出2个Cat 2。这些需要在它们之间完全重新分配。例如，T0的一个Cat0给T1，一个Cat0给T2；T1的一个Cat1给T0，一个Cat1给T2；T2的一个Cat2给T0，一个Cat2给T1。这可以通过3次类型间的两两交换完成。
五、解题思路
1、最大化S：
- 要使 S 最大，我们应该让每个三元组中贡献给 S 的那个“中间”元素尽可能大。
- 首先，对输入的 n 个数字进行排序。
- 将排序后的数字分成三组：
- S_small：最小的 n/3 个数字。
- S_middle：中间的 n/3 个数字。
- S_large：最大的 n/3 个数字。
- 为了使 S 最大，每个形成的三元组必须包含一个来自 S_small 的数字，一个来自 S_middle 的数字，和一个来自 S_large 的数字。这样，来自 S_middle 组的数字将自然成为该三元组的中间值（数值上不大不小）。
- 因此，最大化的 S 就是 S_middle 组中所有数字的总和。
2、最小化移动次数：
- 我们的目标是将原始数组重新排列，使得每三个连续的元素（一个三元组）都包含来自 S_small、S_middle、S_large 各一个元素。
- 这个问题可以转化为计算最少的“交换操作”次数，以纠正类型错配。
- 首先，根据上述分类方法，确定原始数组中每个元素的类别（属于 S_small 为类别0，S_middle 为类别1，S_large 为类别2）。
- 然后，分析每个实际的三元组（即原始数组中每三个连续的元素）：
- 统计每个三元组中各个类别元素的数量。
- 如果一个三元组中某个类别的元素超过1个，则多余的元素是“盈余”元素。
- 如果一个三元组中某个类别的元素数量为0，则该类别是“亏损”类别。
- 对于每个三元组，其盈余元素的总数必然等于其亏损类别的总数。我们将这些盈余元素视为需要“流向”亏损类别的元素。例如，如果一个三元组有2个类别0的元素和0个类别1的元素（其他元素正常），那么它有一个盈余的类别0元素，需要一个类别1元素。我们可以认为这个盈余的类别0元素需要“变成”类别1元素（通过与其他三元组的元素交换）。
- 我们统计全局的“流量”：effective_flow[i][j] 表示有多少个原本属于类别 i 的元素，为了满足平衡，最终需要扮演类别 j 的角色（即从一个有类别 i 盈余、类别 j 亏损的三元组流出，去补充另一个三元组的类别 j 亏损）。
- 这个 effective_flow 矩阵（考虑 i != j 的部分）描述了不同类别之间的转换需求。例如，effective_flow[0][1]=k 表示有 k 个类别0的元素需要转变成类别1。
- 这种转换可以通过元素交换实现。我们需要计算最少的交换操作次数。这可以通过分析类型之间的流向图（包含类型0、1、2的节点）来解决：
- 计算两两类型之间的直接交换数量：例如，类型0流向类型1的数量 f[0][1] 和类型1流向类型0的数量 f[1][0]，则可以直接交换 min(f[0][1], f[1][0]) 次。
- 减去这些直接交换后，剩余的流量会形成三元环流（例如，类型0->类型1，类型1->类型2，类型2->类型0）。每个这样的三元环流需要2次交换操作。
- 总的交换次数就是这些直接交换和三元环交换的总和。题目中的“移动次数”根据示例推断，应该是指这种“交换操作”的次数，而不是单个元素的物理移动次数（一次交换操作会移动2个元素）。
六、Python算法源码
import collections
def solve():
line = input() # 读取输入行
str_nums = line.split(" ") # 按空格分割
n = len(str_nums) # 数组长度
arr = [int(s) for s in str_nums] # 转换为整数数组
# 1. 排序以确定类别阈值
sorted_arr = sorted(arr) # 排序数组
n_div_3 = n // 3 # n/3
threshold_small_middle = sorted_arr[n_div_3 - 1] # S_small 和 S_middle 的分界值
threshold_middle_large = sorted_arr[2 * n_div_3 - 1] # S_middle 和 S_large 的分界值
# 2. 为原数组每个元素分类
arr_categories = [0] * n # 存储每个元素的类别
for i in range(n):
if arr[i] <= threshold_small_middle:
arr_categories[i] = 0 # S_small 类别
elif arr[i] <= threshold_middle_large:
arr_categories[i] = 1 # S_middle 类别
else:
arr_categories[i] = 2 # S_large 类别
# 3. 计算 effective_flow 矩阵
effective_flow = [[0, 0, 0] for _ in range(3)] # effective_flow[from_type][to_type]
num_triplets = n // 3
for k in range(num_triplets):
actual_counts_in_triplet = [0, 0, 0] # 当前三元组中各类别的数量
actual_counts_in_triplet[arr_categories[3 * k]] += 1
actual_counts_in_triplet[arr_categories[3 * k + 1]] += 1
actual_counts_in_triplet[arr_categories[3 * k + 2]] += 1
surplus_types_in_triplet = [] # 记录多余的类型
deficit_types_in_triplet = [] # 记录缺失的类型
for type_val in range(3):
if actual_counts_in_triplet[type_val] > 1: # 如果该类型元素多于1个
for _ in range(actual_counts_in_triplet[type_val] - 1):
surplus_types_in_triplet.append(type_val) # 添加到多余列表
if actual_counts_in_triplet[type_val] == 0: # 如果该类型元素为0个
deficit_types_in_triplet.append(type_val) # 添加到缺失列表
# 配对多余和缺失的类型以记录流量
for i in range(len(surplus_types_in_triplet)):
from_type = surplus_types_in_triplet[i]
to_type = deficit_types_in_triplet[i]
effective_flow[from_type][to_type] += 1
# 4. 计算交换次数
f = [[0, 0, 0] for _ in range(3)] # f[i][j] 表示类型 i 流向类型 j 的数量 (i != j)
for i in range(3):
for j in range(3):
if i != j:
f[i][j] = effective_flow[i][j]
swaps = 0 # 初始化交换次数
# 处理两两类型间的直接交换
direct_swap_01 = min(f[0][1], f[1][0])
swaps += direct_swap_01
f[0][1] -= direct_swap_01
f[1][0] -= direct_swap_01
direct_swap_02 = min(f[0][2], f[2][0])
swaps += direct_swap_02
f[0][2] -= direct_swap_02
f[2][0] -= direct_swap_02
direct_swap_12 = min(f[1][2], f[2][1])
swaps += direct_swap_12
f[1][2] -= direct_swap_12
f[2][1] -= direct_swap_12
# 处理三类型间的循环交换
# 0->1->2->0 环流
cycle_012_count = min(f[0][1], f[1][2], f[2][0])
swaps += 2 * cycle_012_count # 每个3元环贡献2次交换
# 0->2->1->0 环流
cycle_021_count = min(f[0][2], f[2][1], f[1][0])
swaps += 2 * cycle_021_count # 每个3元环贡献2次交换
print(swaps) # 输出结果
solve()
七、JavaScript算法源码
const readline = require('readline'); // Node.js环境下用于读取输入
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal: false // 设置为false以避免在非交互式环境中的问题
});
rl.on('line', (line) => { // 当读取到一行输入时执行
const strNums = line.split(" "); // 按空格分割
const n = strNums.length; // 数组长度
const arr = strNums.map(s => parseInt(s)); // 转换为整数数组
// 1. 排序以确定类别阈值
const sortedArr = [...arr].sort((a, b) => a - b); // 创建副本并排序
const n_div_3 = Math.floor(n / 3); // n/3
const threshold_small_middle = sortedArr[n_div_3 - 1]; // S_small 和 S_middle 的分界值
const threshold_middle_large = sortedArr[2 * n_div_3 - 1]; // S_middle 和 S_large 的分界值
// 2. 为原数组每个元素分类
const arrCategories = new Array(n).fill(0); // 存储每个元素的类别
for (let i = 0; i < n; i++) {
if (arr[i] <= threshold_small_middle) {
arrCategories[i] = 0; // S_small 类别
} else if (arr[i] <= threshold_middle_large) {
arrCategories[i] = 1; // S_middle 类别
} else {
arrCategories[i] = 2; // S_large 类别
}
}
// 3. 计算 effective_flow 矩阵
const effectiveFlow = Array(3).fill(null).map(() => Array(3).fill(0)); // effective_flow[from_type][to_type]
const numTriplets = Math.floor(n / 3);
for (let k = 0; k < numTriplets; k++) {
const actualCountsInTriplet = [0, 0, 0]; // 当前三元组中各类别的数量
actualCountsInTriplet[arrCategories[3 * k]]++;
actualCountsInTriplet[arrCategories[3 * k + 1]]++;
actualCountsInTriplet[arrCategories[3 * k + 2]]++;
const surplusTypesInTriplet = []; // 记录多余的类型
const deficitTypesInTriplet = []; // 记录缺失的类型
for (let typeVal = 0; typeVal < 3; typeVal++) {
if (actualCountsInTriplet[typeVal] > 1) { // 如果该类型元素多于1个
for (let count = 0; count < actualCountsInTriplet[typeVal] - 1; count++) {
surplusTypesInTriplet.push(typeVal); // 添加到多余列表
}
}
if (actualCountsInTriplet[typeVal] === 0) { // 如果该类型元素为0个
deficitTypesInTriplet.push(typeVal); // 添加到缺失列表
}
}
// 配对多余和缺失的类型以记录流量
for (let i = 0; i < surplusTypesInTriplet.length; i++) {
const fromType = surplusTypesInTriplet[i];
const toType = deficitTypesInTriplet[i];
effectiveFlow[fromType][toType]++;
}
}
// 4. 计算交换次数
const f = Array(3).fill(null).map(() => Array(3).fill(0)); // f[i][j] 表示类型 i 流向类型 j 的数量 (i != j)
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (i !== j) {
f[i][j] = effectiveFlow[i][j];
}
}
}
let swaps = 0; // 初始化交换次数
// 处理两两类型间的直接交换
let direct_swap_01 = Math.min(f[0][1], f[1][0]);
swaps += direct_swap_01;
f[0][1] -= direct_swap_01;
f[1][0] -= direct_swap_01;
let direct_swap_02 = Math.min(f[0][2], f[2][0]);
swaps += direct_swap_02;
f[0][2] -= direct_swap_02;
f[2][0] -= direct_swap_02;
let direct_swap_12 = Math.min(f[1][2], f[2][1]);
swaps += direct_swap_12;
f[1][2] -= direct_swap_12;
f[2][1] -= direct_swap_12;
// 处理三类型间的循环交换
// 0->1->2->0 环流
let cycle_012_count = Math.min(f[0][1], f[1][2], f[2][0]);
swaps += 2 * cycle_012_count; // 每个3元环贡献2次交换
// 0->2->1->0 环流
let cycle_021_count = Math.min(f[0][2], f[2][1], f[1][0]);
swaps += 2 * cycle_021_count; // 每个3元环贡献2次交换
console.log(swaps); // 输出结果
rl.close(); // 关闭读取接口
});
八、C算法源码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> // 为了 INT_MAX
// 比较函数，用于 qsort
int compare_integers(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// min 函数的简单实现
int min(int a, int b) {
return a < b ? a : b;
}
int min3(int a, int b, int c){
return min(a, min(b,c));
}
// 计算 effective_flow 的辅助函数
void calculate_effective_flow_c(int n, int* arr_categories, int effective_flow[3][3]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
effective_flow[i][j] = 0;
}
}
int num_triplets = n / 3;
for (int k = 0; k < num_triplets; k++) {
int actual_counts_in_triplet[3] = {0, 0, 0};
actual_counts_in_triplet[arr_categories[3 * k]]++;
actual_counts_in_triplet[arr_categories[3 * k + 1]]++;
actual_counts_in_triplet[arr_categories[3 * k + 2]]++;
// C中动态列表不方便，这里用固定大小数组模拟，假设盈余/亏损类型不会太多
int surplus_types_in_triplet[2]; // 一个三元组最多有两个同类型盈余 (e.g., 0,0,0)
int deficit_types_in_triplet[2]; // 最多亏损两个类型
int surplus_count = 0;
int deficit_count = 0;
for (int type_val = 0; type_val < 3; type_val++) {
if (actual_counts_in_triplet[type_val] > 1) {
for (int c = 0; c < actual_counts_in_triplet[type_val] - 1; c++) {
if (surplus_count < 2) surplus_types_in_triplet[surplus_count++] = type_val;
}
}
if (actual_counts_in_triplet[type_val] == 0) {
if (deficit_count < 2) deficit_types_in_triplet[deficit_count++] = type_val;
}
}
for (int i = 0; i < surplus_count; i++) { // surplus_count 应该等于 deficit_count
int from_type = surplus_types_in_triplet[i];
int to_type = deficit_types_in_triplet[i]; // 简单顺序匹配
effective_flow[from_type][to_type]++;
}
}
}
int main() {
char line[1200]; // 假设行长度不超过 1200 (600数字 * 2字符(数字+空格))
if (fgets(line, sizeof(line), stdin) == NULL) { // 读取一行输入
return 1; // 读取失败
}
line[strcspn(line, "\n")] = 0; // 移除可能的换行符
int arr[600]; // 最大n为600
int n = 0;
char *token = strtok(line, " "); // 按空格分割
while (token != NULL && n < 600) {
arr[n++] = atoi(token); // 转换为整数
token = strtok(NULL, " ");
}
// 1. 排序以确定类别阈值
int sorted_arr[600];
for(int i=0; i<n; ++i) sorted_arr[i] = arr[i]; // 复制数组
qsort(sorted_arr, n, sizeof(int), compare_integers); // 排序
int n_div_3 = n / 3;
int threshold_small_middle = sorted_arr[n_div_3 - 1];
int threshold_middle_large = sorted_arr[2 * n_div_3 - 1];
// 2. 为原数组每个元素分类
int arr_categories[600];
for (int i = 0; i < n; i++) {
if (arr[i] <= threshold_small_middle) {
arr_categories[i] = 0;
} else if (arr[i] <= threshold_middle_large) {
arr_categories[i] = 1;
} else {
arr_categories[i] = 2;
}
}
// 3. 计算 effective_flow 矩阵
int effective_flow[3][3];
calculate_effective_flow_c(n, arr_categories, effective_flow);
// 4. 计算交换次数
int f[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i != j) {
f[i][j] = effective_flow[i][j];
} else {
f[i][j] = 0; // 对角线不参与这里的计算
}
}
}
int swaps = 0;
// 处理两两类型间的直接交换
int direct_swap_01 = min(f[0][1], f[1][0]);
swaps += direct_swap_01;
f[0][1] -= direct_swap_01;
f[1][0] -= direct_swap_01;
int direct_swap_02 = min(f[0][2], f[2][0]);
swaps += direct_swap_02;
f[0][2] -= direct_swap_02;
f[2][0] -= direct_swap_02;
int direct_swap_12 = min(f[1][2], f[2][1]);
swaps += direct_swap_12;
f[1][2] -= direct_swap_12;
f[2][1] -= direct_swap_12;
// 处理三类型间的循环交换
int cycle_012_count = min3(f[0][1], f[1][2], f[2][0]);
swaps += 2 * cycle_012_count;
int cycle_021_count = min3(f[0][2], f[2][1], f[1][0]);
swaps += 2 * cycle_021_count;
printf("%d\n", swaps); // 输出结果
return 0;
}
九、C++算法源码
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm> // For std::sort, std::min
#include <numeric> // For std::iota (potentially)
// 计算 effective_flow 的辅助函数
std::vector<std::vector<int>> calculate_effective_flow_cpp(int n, const std::vector<int>& arr_categories) {
std::vector<std::vector<int>> effective_flow(3, std::vector<int>(3, 0));
int num_triplets = n / 3;
for (int k = 0; k < num_triplets; ++k) {
std::vector<int> actual_counts_in_triplet(3, 0);
actual_counts_in_triplet[arr_categories[3 * k]]++;
actual_counts_in_triplet[arr_categories[3 * k + 1]]++;
actual_counts_in_triplet[arr_categories[3 * k + 2]]++;
std::vector<int> surplus_types_in_triplet;
std::vector<int> deficit_types_in_triplet;
for (int type_val = 0; type_val < 3; ++type_val) {
if (actual_counts_in_triplet[type_val] > 1) {
for (int count = 0; count < actual_counts_in_triplet[type_val] - 1; ++count) {
surplus_types_in_triplet.push_back(type_val);
}
}
if (actual_counts_in_triplet[type_val] == 0) {
deficit_types_in_triplet.push_back(type_val);
}
}
for (size_t i = 0; i < surplus_types_in_triplet.size(); ++i) {
int from_type = surplus_types_in_triplet[i];
int to_type = deficit_types_in_triplet[i]; // 简单顺序匹配
effective_flow[from_type][to_type]++;
}
}
return effective_flow;
}
int main() {
std::ios_base::sync_with_stdio(false); // 加速C++ IO
std::cin.tie(NULL); // 解除 cin 和 cout 的绑定
std::string line;
std::getline(std::cin, line); // 读取一行输入
std::stringstream ss(line); // 用于分割字符串
std::string segment;
std::vector<int> arr;
while (std::getline(ss, segment, ' ')) { // 按空格分割
if (!segment.empty()) {
arr.push_back(std::stoi(segment)); // 转换为整数并添加到vector
}
}
int n = arr.size(); // 数组长度
// 1. 排序以确定类别阈值
std::vector<int> sorted_arr = arr; // 复制数组
std::sort(sorted_arr.begin(), sorted_arr.end()); // 排序
int n_div_3 = n / 3;
int threshold_small_middle = sorted_arr[n_div_3 - 1];
int threshold_middle_large = sorted_arr[2 * n_div_3 - 1];
// 2. 为原数组每个元素分类
std::vector<int> arr_categories(n);
for (int i = 0; i < n; ++i) {
if (arr[i] <= threshold_small_middle) {
arr_categories[i] = 0;
} else if (arr[i] <= threshold_middle_large) {
arr_categories[i] = 1;
} else {
arr_categories[i] = 2;
}
}
// 3. 计算 effective_flow 矩阵
std::vector<std::vector<int>> effective_flow = calculate_effective_flow_cpp(n, arr_categories);
// 4. 计算交换次数
std::vector<std::vector<int>> f(3, std::vector<int>(3, 0));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (i != j) {
f[i][j] = effective_flow[i][j];
}
}
}
int swaps = 0;
// 处理两两类型间的直接交换
int direct_swap_01 = std::min(f[0][1], f[1][0]);
swaps += direct_swap_01;
f[0][1] -= direct_swap_01;
f[1][0] -= direct_swap_01;
int direct_swap_02 = std::min(f[0][2], f[2][0]);
swaps += direct_swap_02;
f[0][2] -= direct_swap_02;
f[2][0] -= direct_swap_02;
int direct_swap_12 = std::min(f[1][2], f[2][1]);
swaps += direct_swap_12;
f[1][2] -= direct_swap_12;
f[2][1] -= direct_swap_12;
// 处理三类型间的循环交换
int cycle_012_count = std::min({f[0][1], f[1][2], f[2][0]}); // C++11 initializer list for min
swaps += 2 * cycle_012_count;
int cycle_021_count = std::min({f[0][2], f[2][1], f[1][0]});
swaps += 2 * cycle_021_count;
std::cout << swaps << std::endl; // 输出结果
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2025 B卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
扫一扫
668
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
