---

(1)

首先将集合A排序：

若n为奇数，则|n1-n2|=1，选择前n/2个元素为A1，剩余的元素为A2。

若n为偶数，则|n1-n2|=0，选择前n/2个元素为A1，剩余的元素为A2。。

(2)

// 进行归并排序

void mergesort(vector<int> &A, int l, int r)

{

  if (l == r)

    return;

  int mid = l + r >> 1;

  mergesort(A, l, mid);

  mergesort(A, mid + 1, r);

  // 进行二路归并

  vector<int>temp;

  int i = l, j = mid + 1, cnt = r - l + 1;

  while(cnt--) {

    if (i <= mid && A[i] < A[j])

      temp.push_back(A[i++]);

    else

      temp.push_back(A[j++]);

  }

  for(int i = l; i <= r; i++)

    A[i] = temp[i - l];

}

 

std::pair<vector<int>, vector<int> > solve(vector<int> &A)

{

  int n = A.size();

  int m = n / 2;

  mergesort(A, 0, n - 1);

  vector<int>A1, A2;

  for(int i = 0; i &...