REALHW90 基因序列分组优化

题目链接

题目描述

在一个基因工程研究项目中，科学家们获得了一批基因序列样本 $S$ 。这批样本的数量为 $N$ ，其中 $N$ 是一个偶数。每个基因序列都有一个整数ID。为了进行对比实验，需要将这批样本 $S$ 分成两个小组：实验组 $A$ 和对照组 $B$ 。

分组必须遵循以下严格的实验标准：

数量均等: 两个小组的基因序列样本数量必须完全相等，即 $|A| = |B| = N/2$ 。
组内ID唯一性: 在同一个小组内，所有基因序列的ID必须是唯一的。
有序排列: 输出时，两个小组内的基因序列ID都必须按升序排列。
实验组复杂度最小化: 实验组 $A$ 的“基因复杂度”（定义为组内所有ID的总和）必须达到最小值。

您的任务是设计一个算法，根据给定的初始样本集合 $S$ ，找出满足上述所有条件的最优分组方案。

解题思路

这是一个分组优化问题，其核心在于如何在满足约束条件的前提下找到最优解。通过分析题目要求，可以发现这是一个典型的贪心问题。解决策略可以分为三步：处理无解情况、处理必须的强制分配、对剩余部分进行贪心选择。

预处理与无解情况判断 首先，我们需要统计每个ID的出现频率。根据“组内ID唯一性”的规则，任何一个ID在单个组内最多只能出现一次。由于我们只有两个组，所以任何ID在总样本中最多只能出现两次。如果一个ID出现了三次或更多次，根据鸽巢原理，必然至少有两个相同的ID被分到同一组，从而违反规则。因此，如果任何ID的出现次数大于2，则问题无解，直接输出null。
确定性分配（强制分配） 对于那些出现次数恰好为2次的ID（我们称之为“成对ID”），它们必须被分到不同的组中才能满足唯一性。因此，我们可以直接将每个成对ID的一个副本放入实验组 $A$ ，另一个副本放入对照组 $B$ 。这部分的分配是没有选择余地的，是确定性的。
贪心选择（优化分配） 处理完成对ID后，剩下的都是只出现了1次的ID（我们称之为“单一ID”）。这些ID是我们进行优化分配的部分。题目要求最小化实验组 $A$ 的ID总和。由于成对ID对两组总和的贡献是相同的，所以为了实现这一目标，我们应该将值最小的单一ID分配给实验组 $A$ 。具体做法是： a. 将所有单一ID收集起来并按升序排序。 b. 将排序后前半部分的单一ID全部分配给实验组 $A$ 。 c. 将排序后后半部分的单一ID全部分配给对照组 $B$ 。
输出完成所有分配后，分别对实验组 $A$ 和对照组 $B$ 的最终ID列表进行升序排序，然后按格式要求输出。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

void print_vector(const vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec[i] << (i == vec.size() - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    string line;
    getline(cin, line);
    if (line.empty()) {
        cout << "null" << endl;
        return 0;
    }
    
    stringstream ss(line);
    vector<int> ids;
    int num;
    while (ss >> num) {
        ids.push_back(num);
    }
    
    map<int, int> counts;
    for (int id : ids) {
        counts[id]++;
    }

    for (auto const& [id, count] : counts) {
        if (count > 2) {
            cout << "null" << endl;
            return 0;
        }
    }

    vector<int> group_a;
    vector<int> group_b;
    vector<int> singles;

    for (auto const& [id, count] : counts) {
        if (count == 2) {
            group_a.push_back(id);
            group_b.push_back(id);
        } else {
            singles.push_back(id);
        }
    }

    // singles 已经是按键（ID）排序的
    int num_singles_for_a = singles.size() / 2;
    for (int i = 0; i < num_singles_for_a; ++i) {
        group_a.push_back(singles[i]);
    }
    for (size_t i = num_singles_for_a; i < singles.size(); ++i) {
        group_b.push_back(singles[i]);
    }

    sort(group_a.begin(), group_a.end());
    sort(group_b.begin(), group_b.end());

    print_vector(group_a);
    print_vector(group_b);

    return 0;
}

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        
        if (line == null || line.trim().isEmpty()) {
            System.out.println("null");
            return;
        }

        String[] parts = line.split("\\s+");
        List<Integer> ids = new ArrayList<>();
        for (String part : parts) {
            ids.add(Integer.parseInt(part));
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int id : ids) {
            counts.put(id, counts.getOrDefault(id, 0) + 1);
        }

        for (int count : counts.values()) {
            if (count > 2) {
                System.out.println("null");
                return;
            }
        }

        List<Integer> groupA = new ArrayList<>();
        List<Integer> groupB = new ArrayList<>();
        List<Integer> singles = new ArrayList<>();

        List<Integer> sortedKeys = new ArrayList<>(counts.keySet());
        Collections.sort(sortedKeys);

        for (int id : sortedKeys) {
            if (counts.get(id) == 2) {
                groupA.add(id);
                groupB.add(id);
            } else {
                singles.add(id);
            }
        }

        int numSinglesForA = singles.size() / 2;
        for (int i = 0; i < numSinglesForA; i++) {
            groupA.add(singles.get(i));
        }
        for (int i = numSinglesForA; i < singles.size(); i++) {
            groupB.add(singles.get(i));
        }

        Collections.sort(groupA);
        Collections.sort(groupB);

        System.out.println(groupA.stream().map(String::valueOf).collect(Collectors.joining(" ")));
        System.out.println(groupB.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

from collections import Counter

def solve():
    line = input()
    if not line:
        print("null")
        return
        
    ids = list(map(int, line.split()))
    
    counts = Counter(ids)
    
    if any(count > 2 for count in counts.values()):
        print("null")
        return
        
    group_a = []
    group_b = []
    singles = []
    
    # 对ID进行排序以保证处理顺序，从而使singles列表自然有序
    for id_val in sorted(counts.keys()):
        if counts[id_val] == 2:
            group_a.append(id_val)
            group_b.append(id_val)
        else:
            singles.append(id_val)
            
    num_singles_for_a = len(singles) // 2
    
    group_a.extend(singles[:num_singles_for_a])
    group_b.extend(singles[num_singles_for_a:])
    
    group_a.sort()
    group_b.sort()
    
    print(*group_a)
    print(*group_b)

solve()

算法及复杂度

算法: 贪心算法
时间复杂度: $O(N \log N)$ ，其中 $N$ 是基因序列的总数。时间复杂度的瓶颈主要在于对所有唯一的ID进行排序，或者在最后对两个分组结果进行排序。频率统计本身的时间复杂度为 $O(N)$ 。
空间复杂度: $O(K)$ ，其中 $K$ 是不同ID的数量（ $K \le N$ ）。主要用于存储ID的频率映射以及最终的分组列表。

题解 | #基因序列分组优化#

REALHW90 基因序列分组优化

题目链接

题目描述

解题思路

代码

算法及复杂度