华为 · 排序 · 算法编程题
华为 排序 N ≤ 500 时限 3 秒 / 256 MB

题目描述

在一个基因工程研究项目中,科学家们获得了一批基因序列样本 G_0 。
这批样本的数量为 N ,其中 N 是一个偶数,且 1 ≤ N ≤ 500 。
每个基因序列都有一个整数ID,ID值可能会重复出现。
为了进行对比实验,需要将这批样本 G_0 分成两个小组:实验组 G_A 和对照组 G_B 。
分组必须遵循以下严格的实验标准:
1. 数量均等 : 两个小组的基因序列样本数量必须完全相等,即 |G_A| = |G_B| = (N/2) 。
2. 组内ID唯一性 : 在同一个小组内,所有基因序列的ID必须是唯一的。
3. 有序排列 : 输出时,两个小组内的基因序列ID都必须按升序排列。
4. 实验组复杂度最小化 : 为了确保实验结果的准确性,实验组 G_A 的“基因复杂度”(定义为组内所有ID的总和 Σ_id ∈ G_A id )必须达到最小值。
您的任务是设计一个算法,根据给定的初始样本集合 G_0 ,找出满足上述所有条件的最优分组方案。
如果存在这样的方案,请输出两个小组的ID列表。
如果无法找到任何满足条件的分组方案,则输出 `null`。

输入输出

输入描述
一个包含 N 个正整数的数组,代表初始基因序列样本集合 G_0 的ID列表。
数组长度 N 的范围为 [1, 500] 。
输出描述
如果存在有效分组,输出两行。
第一行是实验组 G_A 的ID列表(升序),第二行是对照组 G_B 的ID列表(升序)。
ID之间用空格隔开。
如果不存在有效分组,则输出字符串 `null`。

样例共 2 组

样例 1
输入
1 1 2 4 3 6
输出
1 2 3
1 4 6
样例 2
输入
1 1 1 2
输出
null

算法解析依据一般

考点:排序

数据规模 N ≤ 500 | 限制 3 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:N ≤ 500
  • 复杂度门槛:允许 O(n²);若 n ≤ 300,O(n³) 通常也跑得动,需看具体常数。
  • 源站时限:3 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:排序

先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。

思路框架(排序 通法 · 非本题专属)

  1. 排序后很多性质变简单:相邻关系、前缀性质、二分可行。
  2. 若题目禁止使用排序库函数,则手写快排/归并(归并还能顺带求逆序对)。
  3. 排序常与其他范式组合,比如「排序 + 贪心」「排序 + 二分」「排序 + 双指针」。

实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。

复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)

该范式的通法易错点

  • 自定义比较函数不满足严格弱序会导致运行时崩溃。
  • 排序后丢失原始下标,题目需要下标时记得用 pair 一起排。

对照本题

  • 数据规模 N ≤ 500,允许 O(n²);若 n ≤ 300,O(n³) 通常也跑得动,需看具体常数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:1 1 2 4 3 6
  • 输出:1 2 3 / 1 4 6

样例 2

  • 输入:1 1 1 2
  • 输出:null

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-11月06号留学生开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解