1. 元素数尽量平衡：

   • 首先，将元素个数尽可能平均分配。
   • 这意味着我们希望 n1 ≈ n/2 和 n2 ≈ n/2（如果 n 是偶数，两个子集都是 n/2；如果是奇数，则差距为1）。

2. 最大化差值的和：

   • 为了让 |S1 - S2| 最大，我们希望两个子集的元素之和差异最大。
   • 一种策略是：
     • 将最大元素全部放在一个子集，剩余元素放在另一个子集。
     • 可以选择把最大元素放在A1或A2中，放在哪一边都可以，只要保证两个子集大小差异尽量小（1个元素差或相等），就能保证和差尽可能大。

3. 具体方案：

   • 对数组排序（降序或升序均可）。
   • 根据 n 的奇偶性，将前面较大的元素分配到A1，将剩余元素分配到A2（或反过来）。
   • 调整元素分配，使两个子集大小差不超过1。

（2）

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}
...