解题思路

• 算法：计数 + 贪心

• 核心想法

  1. 统计每个号码出现次数。若某个号码出现 超过 2 次，则无法把它放入两队（每队内不能重复），直接返回 null。
  2. 将出现 2 次 的号码记为 pairs（它们必须一左一右各放一个）；出现 1 次 的号码记为 singles（可任选放在哪一队）。
  3. 设队伍总人数为 n，每队人数应为 k = n/2。pairs 中的号码会让两队各占用一个名额，剩余的名额由 singles 填充。
  4. 为了让 n1 的元素和最小：在 singles 升序后，取最小的 k - |pairs| 个放入 n1，其余放入 n2。最后两队分别排序输出。

  证明直观：pairs 中每个数无论如何 n1 都得拿一个，只有 singles 的归属可选，显然把更小的给 n1 才能使其和最小。

复杂度分析

• 设不同号码个数为 m（m ≤ n ≤ 500）。
• 时间复杂度：O(n log n)（主要为排序）。
• 空间复杂度：O(m)（计数与结果存储）。

代码实现

Python

# 功能函数：根据题意分队；不可行则返回 None
def build_teams(a):
    from collections import Counter
    cnt = Counter(a)
    # 若某个号码超过 2 次，无法满足每队不重复
    if any(v > 2 for v in cnt.values()):
        return None

    pairs = []   # 出现 2 次的号码
    singles = [] # 出现 1 次的号码
    for num, c in cnt.items():
        if c == 2:
            pairs.append(num)
        else:
            singles.append(num)

    pairs.sort()
    singles.sort()

    n = len(a)
    k = n // 2

    n1 = pairs[:]  # 每个出现 2 次的号码，两队各放 1 个
    n2 = pairs[:]
    need = k - len(pairs)  # n1 还需要从 singles 里取的个数

    # 贪心：把最小的 need 个单次号码给 n1，其余给 n2
    n1.extend(singles[:need])
    n2.extend(singles[need:])

    n1.sort()
    n2.sort()
    return n1, n2

def parse_input_to_array(s):
    # 将输入字符串解析为整数数组：
    # 1) 若只有一个无空格数字串，如 "112436"，按字符拆成数组
    # 2) 否则按空格分隔为整数
    tokens = s.strip().split()
    if len(tokens) == 1 and tokens[0].isdigit():
        return [int(ch) for ch in tokens[0]]
    else:
        return [int(x) for x in tokens]

def main():
    import sys
    data = sys.stdin.read()
    arr = parse_input_to_array(data)
    res = build_teams(arr)
    if res is None:
        print("null")
    else:
        n1, n2 = res
        print(" ".join(map(str, n1)))
        print(" ".join(map(str, n2)))

if __name__ == "__main__":
    main()

Java

import java.util.*;

/** ACM 风格主类 */
public class Main {

    // 功能函数：根据题意分队；不可行返回 null
    static List<List<Integer>> buildTeams(int[] a) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : a) cnt.put(x, cnt.getOrDefault(x, 0) + 1);

        // 出现次数超过 2 次则无解
        for (int v : cnt.values()) if (v > 2) return null;

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

        int n = a.length, k = n / 2;
        List<Integer> n1 = new ArrayList<>(pairs);
        List<Integer> n2 = new ArrayList<>(pairs);

        int need = k - pairs.size(); // n1 还需从 singles 取的数量
        for (int i = 0; i < singles.size(); i++) {
            if (i < need) n1.add(singles.get(i));
            else n2.add(singles.get(i));
        }
        Collections.sort(n1);
        Collections.sort(n2);

        List<List<Integer>> ans = new ArrayList<>();
        ans.add(n1);
        ans.add(n2);
        return ans;
    }

    // 将输入解析为整数数组：
    // 1) 若只有一个无空格数字串，如 "112436"，按字符拆分
    // 2) 否则按空格分隔
    static int[] parseInput(String all) {
        all = all.trim();
        if (all.isEmpty()) return new int[0];
        String[] toks = all.split("\\s+");
        if (toks.length == 1 && toks[0].matches("\\d+")) {
            String s = toks[0];
            int[] a = new int[s.length()];
            for (int i = 0; i < s.length(); i++) a[i] = s.charAt(i) - '0';
            return a;
        } else {
            int[] a = new int[toks.length];
            for (int i = 0; i < toks.length; i++) a[i] = Integer.parseInt(toks[i]);
            return a;
        }
    }

    public static void main(String[] args) {
        // 读取所有输入（ACM 风格）
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        while (sc.hasNextLine()) {
            String line = sc.nextLine();
            sb.append(line).append(' ');
        }
        int[] arr = parseInput(sb.toString());

        List<List<Integer>> res = buildTeams(arr);
        if (res == null) {
            System.out.println("null");
        } else {
            List<Integer> n1 = res.get(0), n2 = res.get(1);
            // 按题意输出，两行分别为两个队列，空格分隔
            for (int i = 0; i < n1.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(n1.get(i));
            }
            System.out.println();
            for (int i = 0; i < n2.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(n2.get(i));
            }
            System.out.println();
        }
    }
}

C++

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

// 功能函数：根据题意分队；返回是否可行
bool build_teams(const vector<int>& a, vector<int>& n1, vector<int>& n2) {
    unordered_map<int,int> cnt;
    for (int x : a) cnt[x]++;

    // 出现次数超过 2 次则无解
    for (auto &kv : cnt) if (kv.second > 2) return false;

    vector<int> pairs, singles;
    for (auto &kv : cnt) {
        if (kv.second == 2) pairs.push_back(kv.first);
        else singles.push_back(kv.first);
    }
    sort(pairs.begin(), pairs.end());
    sort(singles.begin(), singles.end());

    int n = (int)a.size();
    int k = n / 2;

    n1 = pairs; // 出现两次的数，两队各放一个
    n2 = pairs;

    int need = k - (int)pairs.size(); // n1 还需要从 singles 取多少
    for (int i = 0; i < (int)singles.size(); ++i) {
        if (i < need) n1.push_back(singles[i]);
        else n2.push_back(singles[i]);
    }
    sort(n1.begin(), n1.end());
    sort(n2.begin(), n2.end());
    return true;
}

// 将输入解析为整数数组：
// 1) 若只有一个无空格数字串，如 "112436"，按字符拆成数字
// 2) 否则按空格分隔为整数
vector<int> parse_input(const string& all) {
    // 拆分空格
    string s = all;
    vector<string> tokens;
    string cur;
    for (char c : s) {
        if (isspace((unsigned char)c)) {
            if (!cur.empty()) { tokens.push_back(cur); cur.clear(); }
        } else cur.push_back(c);
    }
    if (!cur.empty()) tokens.push_back(cur);

    vector<int> a;
    if (tokens.size() == 1) {
        bool all_digit = !tokens[0].empty();
        for (char c : tokens[0]) if (!isdigit((unsigned char)c)) all_digit = false;
        if (all_digit) {
            for (char c : tokens[0]) a.push_back(c - '0');
            return a;
        }
    }
    for (auto &t : tokens) a.push_back(stoi(t));
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 读取所有输入（ACM 风格）
    string all, line;
    while (getline(cin, line)) {
        all += line;
        all.push_back(' ');
    }
    vector<int> arr = parse_input(all);

    vector<int> n1, n2;
    if (!build_teams(arr, n1, n2)) {
        cout << "null\n";
    } else {
        // 输出两行，空格分隔
        for (size_t i = 0; i < n1.size(); ++i) {
            if (i) cout << ' ';
            cout << n1[i];
        }
        cout << "\n";
        for (size_t i = 0; i < n2.size(); ++i) {
            if (i) cout << ' ';
            cout << n2[i];
        }
        cout << "\n";
    }
    return 0;
}

题目内容

有一队学生进行排队 $n0$，长度$【1,500】$，数量为偶数，每个人手上拿着一个号码牌，号码牌可以重复，现在需要将学生根据号码牌分成两队 $n1$ 和 $n2$，要求:

• 两队的数量相等。

• $n1$ 队列中的号码牌不能重复，$n2$ 队列中的号码牌不能重复。

• $n1$ 和 $n2$ 需从小到大进行排序

• $n1$ 所有的号码牌数字之和最小

如果可以按照要求排成两队则输出该队列 $(n1,n2)$，如果不能按要求分成两队则返回 $null$

输入描述

给定一个正整数数组，长度$【1,500】$

输出描述

两个队列

样例1

输入

1 1 1 2

输出

null

说明

对 $n0$ 进行排队的唯一可行方案是 $n1=[1,1]$ 和 $n2=[1,2]$ 。但 $n1$ 不是由互不相同的元素构成。因此，返回 $null$ 。

样例2

输入

1 1 2 4 3 6

输出

1 2 3
1 4 6

说明

$n1=[1,2,3],n2=[1,4,6]$ $n1$ 的所有数字之和最小