HC02-集合划分算法¶

2016年统考题：集合划分算法¶

问题分析¶

问题描述¶

给定由 n(n≥2) 个正整数组成的集合 A={ak|0≤ak<n}
将 A 划分为两个不相交的子集 A1 和 A2
目标：满足 |n1-n2| 最小且 |S1-S2| 最大

目标分析¶

|n1-n2| 最小：两个子集的元素个数尽可能相等
当 n 为偶数时：n1 = n2 = n/2
当 n 为奇数时：|n1-n2| = 1
|S1-S2| 最大：两个子集的元素和之差尽可能大
需要一个子集包含尽可能小的元素，另一个包含尽可能大的元素

代码实现¶

C
/**
 * 函数 func：将集合A划分为两个子集A1和A2
 * 满足 |n1-n2|最小且|S1-S2|最大
 * 
 * 参数说明：
 * A[] - 原始数组（输入）
 * A1[] - 子集A1（输出）
 * A2[] - 子集A2（输出）
 * n - 数组长度
 * 
 * 算法思想：
 * 1. 先对数组进行排序
 * 2. 将较小的n/2个元素放入A1
 * 3. 将较大的n-n/2个元素放入A2
 */
void func(int A[], int A1[], int A2[], int n) {
    // 步骤1：对数组进行快速排序（升序）
    Quicksort(A, 0, n-1);

    // 步骤2：将前n/2个较小元素放入A1
    for (int i = 0; i < n/2; ++i) {
        A1[i] = A[i];
    }

    // 步骤3：将后n-n/2个较大元素放入A2
    for (int i = n/2; i < n; ++i) {
        A2[i - n/2] = A[i];
    }
}

快速排序实现（考试时需要写出）¶

C
/**
 * 快速排序主函数
 * 参数：arr - 待排序数组，low - 起始下标，high - 结束下标
 */
void Quicksort(int arr[], int low, int high) {
    if (low < high) {
        // 分区操作，返回基准元素的正确位置
        int pivot = Partition(arr, low, high);

        // 递归排序基准左边的子数组
        Quicksort(arr, low, pivot - 1);

        // 递归排序基准右边的子数组
        Quicksort(arr, pivot + 1, high);
    }
}

/**
 * 分区函数：将数组分为两部分
 * 小于等于基准的元素在左边，大于基准的元素在右边
 */
int Partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选择第一个元素作为基准
    int i = low, j = high;

    while (i < j) {
        // 从右向左找第一个小于基准的元素
        while (i < j && arr[j] > pivot) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];  // 将小元素移到左边
        }

        // 从左向右找第一个大于基准的元素
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];  // 将大元素移到右边
        }
    }

    arr[i] = pivot;  // 基准元素放到正确位置
    return i;        // 返回基准元素的位置
}

算法正确性证明¶

1. |n1-n2| 最小的证明¶

C
// 元素分配：
// A1：前 n/2 个元素
// A2：后 n-n/2 个元素

// 当 n 为偶数时：
// n1 = n/2, n2 = n/2
// |n1-n2| = 0 （最小可能值）

// 当 n 为奇数时：
// n1 = n/2 (向下取整), n2 = n - n/2 = n/2 + 1
// |n1-n2| = 1 （最小可能值）

2. |S1-S2| 最大的证明¶

C
// 设排序后数组：a[0] ≤ a[1] ≤ ... ≤ a[n-1]

// A1 = {a[0], a[1], ..., a[n/2-1]}
// A2 = {a[n/2], a[n/2+1], ..., a[n-1]}

// S1 = Σ(i=0 to n/2-1) a[i]
// S2 = Σ(i=n/2 to n-1) a[i]

// |S1-S2| = |S1-S2| = S2-S1（因为S2≥S1）

// 要证明这是最大可能的差值：
// 任何其他划分方式，如果将某个大元素移到A1或小元素移到A2，
// 都会减小|S1-S2|的值

3. 最优性证明¶

假设存在另一种划分方式，使得 |S1'-S2'| > |S1-S2|。

如果这种划分保持了 |n1'-n2'| 最小（即元素个数分配相同）
那么必须有一些较大的元素在较小的集合中，或较小的元素在较大的集合中
这会导致 S1' 增大或 S2' 减小，从而减小 |S1'-S2'|
因此不可能存在更好的划分

复杂度分析¶

时间复杂度¶

步骤	操作	时间复杂度
1	快速排序	O(N log N)
2	分配A1	O(N/2) = O(N)
3	分配A2	O(N/2) = O(N)

总体时间复杂度：O(N log N)

主导项是快速排序的时间复杂度
数组划分的时间复杂度为线性，不影响总体复杂度

空间复杂度¶

空间类型	大小	说明
输入数组	O(N)	给定的数组A
输出数组	O(N)	A1和A2共占用N个空间
快速排序栈空间	O(log N)	递归调用栈的最大深度

总体空间复杂度：O(N)

但题目给出的"O(log N)"可能指的是额外空间复杂度
额外空间复杂度：O(log N)（仅考虑排序的递归栈）

执行过程图解¶

示例1：n=6（偶数）¶

Text Only

原始数组：[3, 1, 4, 2, 5, 0]
排序后：  [0, 1, 2, 3, 4, 5]

划分：
A1：[0, 1, 2]    (前3个较小元素)
A2：[3, 4, 5]    (后3个较大元素)

结果：
n1=3, n2=3 → |n1-n2|=0（最小）
S1=3, S2=12 → |S1-S2|=9（最大）

示例2：n=5（奇数）¶

Text Only

原始数组：[3, 1, 4, 2, 5]
排序后：  [1, 2, 3, 4, 5]

划分：
A1：[1, 2]       (前2个较小元素)
A2：[3, 4, 5]    (后3个较大元素)

结果：
n1=2, n2=3 → |n1-n2|=1（最小）
S1=3, S2=12 → |S1-S2|=9（最大）

算法优化考虑¶

1. 排序算法的选择¶

C
// 考虑到元素范围：0 ≤ ak < n
// 可以使用计数排序（Counting Sort）

void CountingSort(int A[], int n) {
    int count[n];  // 计数数组
    for (int i = 0; i < n; i++) {
        count[i] = 0;
    }

    // 统计每个元素出现次数
    for (int i = 0; i < n; i++) {
        count[A[i]]++;
    }

    // 重新构造有序数组
    int index = 0;
    for (int i = 0; i < n; i++) {
        while (count[i] > 0) {
            A[index++] = i;
            count[i]--;
        }
    }
}

优化后复杂度： - 时间复杂度：O(N) - 空间复杂度：O(N)

2. 原地划分优化¶

C
// 如果不需要保留原数组，可以原地划分
void func_inplace(int A[], int n) {
    Quicksort(A, 0, n-1);
    // A[0..n/2-1] 为A1
    // A[n/2..n-1] 为A2
    // 不需要额外的A1、A2数组
}

延伸知识点¶

1. 相关问题¶

C
// 变体1：要求|S1-S2|最小
// 解法：转换为经典的"分割等和子集"问题
// 使用动态规划解决

// 变体2：要求|n1-n2|最小且S1≈S2
// 解法：贪心算法或动态规划

// 变体3：多子集划分
// 如：将数组划分为k个子集，使最大和最小
// 这是"装箱问题"的变种

2. 实际应用场景¶

C
// 1. 负载均衡
void balance_load(int servers[], int n) {
    func(servers, A1, A2, n);
    // A1分配给一组处理器，A2分配给另一组
}

// 2. 资源分配
void allocate_resources(int tasks[], int n) {
    func(tasks, small_tasks, large_tasks, n);
    // 小任务给新手，大任务给专家
}

// 3. 数据分区
void partition_data(int data[], int n) {
    func(data, A1, A2, n);
    // A1存储在高速存储，A2存储在普通存储
}

3. 理论扩展¶

问题复杂度分类： - 本题：P类问题（多项式时间可解） - 相关问题：分割等和子集是NP完全问题 - 启示：目标函数的微小变化可能导致复杂度的巨大差异

贪心算法的适用性： - 本题的贪心策略是正确的 - 关键在于排序后取两端 - 这种"极端值分离"策略在许多优化问题中有效

4. 考试注意事项¶

C
// 考试时需要特别注意：
// 1. 快速排序代码要完整写出
// 2. 注意边界条件处理
// 3. 时间复杂度分析要准确
// 4. 空间复杂度要区分总空间和额外空间

// 常见错误：
// - 忘记写快排代码
// - 排序方向错误（降序而非升序）
// - 下标计算错误
// - 没有考虑n为奇数的情况

总结¶

该算法通过排序+两端取值的策略，巧妙地同时满足了两个优化目标：

|n1-n2|最小：通过均分或几乎均分元素个数实现
|S1-S2|最大：通过将最小元素和最大元素分别集中实现

算法时间复杂度为 O(N log N)，主要由排序步骤决定。如果利用元素范围的特性，可以进一步优化到 O(N)。这是一个典型的贪心算法应用，体现了"局部最优导致全局最优"的思想。