• 问题描述

已知由n个正整数构成的集合A，将其划分为两个不想交的子集A1和A2，元素个数分别是n1和n2，A1和A2中的元素之和分别为S1和S2，设计一个尽可能高效的算法，满足|n1-n2|最小且|S1-S2|最大。

•  算法思想

n2-n1最小即为两子序列各为一半，且一半的所有元素比另外一半的任意元素都要小

此处可利用快速排序的思想，当当前的枢轴的最终位置是n/2时，则停止排序，对左右序列的元素进行求和做差即可

• 算法实现

void partition(int a[],int low,int high,int n){
	int pivot=a[low];
	int temp_low=low;
	int temp_high=high;
	while(low<high){
		while(low<high&&pivot<=a[high])--high;
		a[low]=a[high];
		while(low<high&&pivot>a[low])++low;
		a[high]=a[low];
	}
	a[low]=pivot;
	
	if(low==n/2)//找到n/2号元素 
	return;
	partition(a,temp_low,low-1,n);
	partition(a,low+1,temp_high,n);
	
}

• 测试用例

#include<stdio.h> 
void partition(int a[],int low,int high,int n){
	int pivot=a[low];
	int temp_low=low;
	int temp_high=high;
	while(low<high){
		while(low<high&&pivot<=a[high])--high;
		a[low]=a[high];
		while(low<high&&pivot>a[low])++low;
		a[high]=a[low];
	}
	a[low]=pivot;
	
	if(low==n/2)//找到n/2号元素 
	return;
	partition(a,temp_low,low-1,n);
	partition(a,low+1,temp_high,n);
	
}
int main(){
	int a[]={10,2,5,6,88,23,25,9};
	partition(a,0,7,8);
	int i,s1=0,s2=0;
	for(i=0;i<4;i++)
		s1+=a[i];
	for(;i<8;i++)
		s2+=a[i];
		printf("%dn",s2-s1);
		printf("%dn",s2);
}

• 运行结果

最后

以上就是爱笑蜻蜓为你收集整理的408真题——划分序列问题描述 算法思想算法实现测试用例运行结果的全部内容，希望文章能够帮你解决408真题——划分序列问题描述 算法思想算法实现测试用例运行结果所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。