题目

已知由 n（n ≥ 2）个正整数构成的集合 A = {a_k | 0 ≤ k < n}，将其划分为两个不相交的子集 A₁ 和 A₂，元素个数分别是 n₁ 和 n₂，A₁ 和 A₂ 中元素之和分别为 S₁ 和 S₂。设计一个尽可能高效的划分算法，满足 |n₁ - n₂| 最小且 |S₁ - S₂| 最大。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：用快速排序的 partition 思想做"找第 ⌊n/2⌋ 小的元素"——把数组划分为左半 ⌊n/2⌋ 个 ≤ pivot、右半 ⌈n/2⌉ 个 ≥ pivot，则左半即 A₁、右半即 A₂，自动满足 |n₁−n₂| 最小且 |S₁−S₂| 最大。

为什么这样划分就同时满足两条要求？

• |n₁ − n₂| 最小 = 0（n 偶）或 1（n 奇）：左右严格各取 ⌊n/2⌋ 和 ⌈n/2⌉ 个，差距最小是显而易见的——再把任何一个元素从一边搬到另一边都会让差变大。
• |S₁ − S₂| 最大：把"最小的 n₁ 个"放进 A₁，"剩下最大的 n₂ 个"放进 A₂——A₁ 中任何元素都 ≤ A₂ 中任何元素。任何打乱都会让 S₁ 变大、S₂ 变小，差就缩了。

怎么找"前 ⌊n/2⌋ 小"而又不全排序？

借快排 partition：

1. 任选 pivot（首元素），一趟扫描把 ≤ pivot 的甩到左、> pivot 的甩到右，得到 pivot 落点 p。
2. 比较 p 与目标位置 k = ⌊n/2⌋：
   • p == k − 1：pivot 正好落在分界点，结束；
   • p < k − 1：左侧不够，去右半段继续 partition；
   • p > k − 1：左侧过多，去左半段继续 partition。
3. 终止时数组前 k 个就是 A₁、后 n − k 个是 A₂，扫一遍累加 S₁、S₂，输出 |S₂ − S₁|。

比全排序快的关键：每轮 partition 只递归"含目标位置的那半"，平均工作量是 ，故平均 O(n)；全排序无差别地处理两半，O(n log n)。

(2) 代码实现

int setDivide(int A[], int n) {
    int low = 0, high = n - 1;
    int k = n / 2;        // 分界后 A[0..k-1] 为 A₁，A[k..n-1] 为 A₂
    int s1 = 0, s2 = 0;

    // partition 找第 k 小（落到下标 k-1 的位置）
    while (low < high) {
        int pivot = A[low];
        int i = low, j = high;
        while (i < j) {
            while (i < j && A[j] >= pivot) j--;
            A[i] = A[j];
            while (i < j && A[i] <= pivot) i++;
            A[j] = A[i];
        }
        A[i] = pivot;                    // pivot 落在 A[i]

        if (i == k - 1) break;           // 落点正好是分界
        else if (i < k - 1) low = i + 1; // 左侧不够，往右半部继续
        else                high = i - 1;
    }

    // 累加 A₁、A₂ 的元素和
    for (int idx = 0; idx < k; idx++) s1 += A[idx];
    for (int idx = k; idx < n; idx++) s2 += A[idx];

    return s2 - s1;          // 题面要求 |S₁ - S₂| 最大；A₂ 全是大数，S₂ ≥ S₁，直接返 S₂ - S₁
}

关键点说明：

• 不要全排序：题目要求"尽可能高效"。全排序也得对，但 O(n log n) 比 partition 法 O(n) 平均慢一档，不拿满分。
• k 取 ⌊n/2⌋ 还是 ⌈n/2⌉：n 偶时无差别；n 奇时两者差 1，按"左半 ⌊n/2⌋ + 右半 ⌈n/2⌉"自然取 n/2，让 A₂ 多一个（最大那个），S₂−S₁ 还会更大一点点。
• 返回 S₂ − S₁ 即 |S₁ − S₂|：因 A₁ 全是较小元素，S₁ ≤ S₂，绝对值就是差本身。

(3) 复杂度分析

• 时间复杂度：平均 （partition 每轮缩到一半，）；最坏 （每次 pivot 都是当前段的极值，partition 退化成 ）。
• 空间复杂度：，原地 partition，只用了 low、high、i、j、pivot、s1、s2 几个标量。