Description
已知由n(n≥2)个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。
Input
多组数据，每组数据两行。第一行为一个整数n，代表数组中有n个元素。第二行为数组中的n个元素（元素之间用空格分隔）。当n等于0时，输入结束。
Output
每组数据输出两行。第一行为子集A1，第二行为子集A2，每两个元素用空格分隔。
Sample Input
4
123 4
5
981 1 1
0
Sample Output
12
34
11
189
参考程序
#include <stdio.h>
#define LEN 20000
int FindMidPosition(int a[],int low,int high)
{
int temp=a[low];
while(1)
{
while(low<high&&a[high]>=temp)
{
high--;
}
if(low>=high)
{
break;
}
a[low++]=a[high];
while(low<high&&a[low]<=temp)
{
low++;
}
if(low>=high)
{
break;
}
a[high--]=a[low];
}
a[low]=temp;
return low;
}
void Divide(int a[],int start,int end,int n)
{
int mid;
while(start<end)
{
mid=FindMidPosition(a,start,end);
if(mid==n/2)
{
break;
}
else if(mid<n/2)
{
start=mid+1;
}
else
{
end=mid-1;
}
}
}
void OutputArray(int a[],int start,int end)
{
int i;
for(i=start;i<=end-1;i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[i]);
}
int main()
{
int n,i;
while(1)
{
scanf("%d",&n);
if(n==0)
{
break;
}
else
{
int a[LEN];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
Divide(a,0,n-1,n);
OutputArray(a,0,n/2-1);
OutputArray(a,n/2,n-1);
}
}
return 0;
}
分析
本题选自2016年考研真题，考点是一趟快速排序的原理和分治法思想。真题如下：
由题意，为了使两个子集数组元素个数差距尽可能小，因而考虑平均分割数组：如果数组元素个数为偶数，则|n1-n2|=0；如果数组元素个数为奇数，则|n1-n2|=1。按照这样的思路，可知在此情况下能使得两个子集数组元素个数差距尽可能小。为了使两个子集数组元素之和的差距尽可能小，应使得较大的一半元素组合，较小的一半元素组合，所以本题最终目的就是找到较小的一半数组和较大的一半数组。考虑中位数这一数字特征，本题化为寻找中位数，比中位数小的是一部分，不小于中位数 的是另一部分。
很简单的做法就是对数组进行排序，随后输出。但这样基于排序的时间复杂度至少是O(nlogn)（快速排序）。这里注意，由于只需要将数组分割，分割的元素不要求有序（集合元素是无序的），所以只需找到这样一个元素（轴枢），它可以将数组一分为二：该元素之前的元素小于它，该元素之后的元素都大于等于它。这样的特征和一趟快排的思路很相似！一趟快排之后，可以将预选的轴枢放到准确的位置上，且满足轴枢之前的元素小于轴枢，轴枢之前的元素大于等于轴枢。但是这样选择的轴枢，不一定就是数组的中位数，所以要进一步判断，对此轴枢元素的下标和数组中间位置进行比较：1、若此位置恰好是数组中央，那么左侧部分就是A1，右侧部分就是A2；2、若此位置位于数组中央位置的右侧，说明中位数应该比此轴枢元素小，而根据一趟快速的特点，为了寻找中位数，自然要到左半段寻找。因此，应递归调用一趟快排函数FindMidPosition；3、若此位置位于数组中央位置的左侧，同理，应递归调用FindMidPosition函数。最终直到达到上面第1中情形。
综上所述，本题和快速排序思路极为相似，分为两步：1.选择轴枢，进行一趟快排，得到轴枢元素的准确位置；2.对此位置和数组中央进行比较，如不在中央，递归处理左（或右）半数组（分治法），直至所得元素位置恰好位于数组中央。
注意：
1、 这里要特别说明，递归处理左半个数组时，end=mid-1，start不变但不一定是0！递归处理右半个数组时，start=mid+1，end不变但不一定是n-1下面的程序段就存在逻辑错误：；
上面的程序会通过上述两个样例输入，但提交后会显示Wrong Answer。
2、 程序的时间复杂度为O(n)，空间复杂度为O(1).下面给出这道考研题的评分细则（满分13分）：；
在提交代码时，若对数组先排序，再输出，会显示“Wrong Answer”的提示。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: