基因序列分组优化

题目分析

给定 个正整数（基因序列 ID），需要将它们等分为实验组和对照组，每组 个。要求：

  1. 每组内 ID 不能重复
  2. 两组内的 ID 分别升序输出
  3. 实验组的 ID 之和最小

如果无法满足条件，输出 "null"。

思路讲解

第一步：频次统计与可行性判断

先统计每个 ID 的出现次数。由于只有两个组且每组内 ID 不能重复，同一个 ID 最多只能出现 2 次（每组放一个）。如果某个 ID 出现了 3 次或更多，则无解，直接输出 "null"。

第二步：分类讨论

将所有 ID 按出现次数分为两类：

  • 双次 ID（出现 2 次）：这些 ID 必须同时出现在两个组中，没有选择余地。
  • 单次 ID（出现 1 次）：这些 ID 只能放进其中一个组，是我们可以自由分配的部分。

设双次 ID 有 个，单次 ID 有 个，则 。每组需要 个元素，其中 个已经被双次 ID 占满，还需要从单次 ID 中各取 个。

因此 必须是偶数，否则无解。

第三步：贪心最小化实验组之和

将所有单次 ID 排序后，把最小的 个分配给实验组，最大的 个分配给对照组。这样实验组的总和一定是所有合法分组方案中最小的。

最后将两组分别排序输出即可。

样例模拟

以输入 1 1 2 4 3 6 为例：

  • 频次：
  • 双次 ID：，单次 ID：
  • ，取最小的 个 给实验组， 给对照组
  • 实验组：，对照组：

复杂度分析

  • 时间复杂度：，瓶颈在排序
  • 空间复杂度：，用于存储频次和分组结果

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x;
    vector<int> a;
    while (cin >> x) {
        a.push_back(x);
    }
    int n = a.size();
    map<int, int> cnt;
    for (int v : a) cnt[v]++;

    for (auto& [v, c] : cnt) {
        if (c > 2) {
            cout << "null" << endl;
            return 0;
        }
    }

    vector<int> doubles, singles;
    for (auto& [v, c] : cnt) {
        if (c == 2) doubles.push_back(v);
        else singles.push_back(v);
    }
    sort(doubles.begin(), doubles.end());
    sort(singles.begin(), singles.end());

    int s = singles.size();
    if (s % 2 != 0) {
        cout << "null" << endl;
        return 0;
    }

    int half = s / 2;
    vector<int> exp_group, ctrl_group;
    for (int v : doubles) exp_group.push_back(v);
    for (int v : doubles) ctrl_group.push_back(v);
    for (int i = 0; i < half; i++) exp_group.push_back(singles[i]);
    for (int i = half; i < s; i++) ctrl_group.push_back(singles[i]);

    sort(exp_group.begin(), exp_group.end());
    sort(ctrl_group.begin(), ctrl_group.end());

    for (int i = 0; i < (int)exp_group.size(); i++) {
        if (i) cout << " ";
        cout << exp_group[i];
    }
    cout << endl;
    for (int i = 0; i < (int)ctrl_group.size(); i++) {
        if (i) cout << " ";
        cout << ctrl_group[i];
    }
    cout << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> a = new ArrayList<>();
        while (sc.hasNextInt()) {
            a.add(sc.nextInt());
        }
        int n = a.size();
        TreeMap<Integer, Integer> cnt = new TreeMap<>();
        for (int v : a) cnt.merge(v, 1, Integer::sum);

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

        List<Integer> doubles = new ArrayList<>(), singles = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            if (e.getValue() == 2) doubles.add(e.getKey());
            else singles.add(e.getKey());
        }

        int s = singles.size();
        if (s % 2 != 0) {
            System.out.println("null");
            return;
        }

        int half = s / 2;
        List<Integer> expGroup = new ArrayList<>(doubles);
        List<Integer> ctrlGroup = new ArrayList<>(doubles);
        for (int i = 0; i < half; i++) expGroup.add(singles.get(i));
        for (int i = half; i < s; i++) ctrlGroup.add(singles.get(i));

        Collections.sort(expGroup);
        Collections.sort(ctrlGroup);

        StringBuilder sb1 = new StringBuilder(), sb2 = new StringBuilder();
        for (int i = 0; i < expGroup.size(); i++) {
            if (i > 0) sb1.append(" ");
            sb1.append(expGroup.get(i));
        }
        for (int i = 0; i < ctrlGroup.size(); i++) {
            if (i > 0) sb2.append(" ");
            sb2.append(ctrlGroup.get(i));
        }
        System.out.println(sb1);
        System.out.println(sb2);
    }
}

import sys
from collections import Counter

def main():
    data = sys.stdin.read().split()
    a = list(map(int, data))
    n = len(a)
    cnt = Counter(a)

    for c in cnt.values():
        if c > 2:
            print("null")
            return

    doubles = sorted(v for v, c in cnt.items() if c == 2)
    singles = sorted(v for v, c in cnt.items() if c == 1)

    s = len(singles)
    if s % 2 != 0:
        print("null")
        return

    half = s // 2
    exp_group = sorted(doubles + singles[:half])
    ctrl_group = sorted(doubles + singles[half:])

    print(" ".join(map(str, exp_group)))
    print(" ".join(map(str, ctrl_group)))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

let lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const a = lines.join(' ').split(/\s+/).filter(x => x).map(Number);
    const n = a.length;
    const cnt = new Map();
    for (const v of a) cnt.set(v, (cnt.get(v) || 0) + 1);

    for (const c of cnt.values()) {
        if (c > 2) {
            console.log("null");
            return;
        }
    }

    const doubles = [], singles = [];
    for (const [v, c] of cnt) {
        if (c === 2) doubles.push(v);
        else singles.push(v);
    }
    doubles.sort((a, b) => a - b);
    singles.sort((a, b) => a - b);

    const s = singles.length;
    if (s % 2 !== 0) {
        console.log("null");
        return;
    }

    const half = s / 2;
    const expGroup = [...doubles, ...singles.slice(0, half)].sort((a, b) => a - b);
    const ctrlGroup = [...doubles, ...singles.slice(half)].sort((a, b) => a - b);

    console.log(expGroup.join(" "));
    console.log(ctrlGroup.join(" "));
});