在一个基因工程研究项目中,科学家们获得了一批基因序列样本 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`。
1 1 2 4 3 6
1 2 3 1 4 6
1 1 1 2
null
考点:排序
数据规模 N ≤ 500 | 限制 3 秒 / 256MB | 标准输入输出
参考方向:排序
先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。
思路框架(排序 通法 · 非本题专属)
实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。
复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
1 1 2 4 3 61 2 3 / 1 4 6样例 2
1 1 1 2null解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2025年秋招-华为-11月06号留学生开发岗。