数据结构实验一，第37题：数组的分割

描述

已知由n(n≥2)个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。

输入

多组数据，每组数据两行。第一行为一个整数n，代表数组中有n个元素。第二行为数组中的n个元素（元素之间用空格分隔）。当n等于0时，输入结束。

输出

每组数据输出两行。第一行为子集A1，第二行为子集A2，每两个元素用空格分隔。

输入样例 1

4
1 2 3 4
5
9 8 1 1 1
0

输出样例 1

1 2
3 4
1 1
1 8 9

害。这一题找错误找三个小时，最后找到错的原因竟然是low=++pivotindex写成了low=pivotindex++QAQ。

代码

#include <bits/stdc++.h>
using namespace std;

int Partition(int a[],int low,int high)
{
	int pivoitkey=a[low];
	while(low<high)
	{
		while(low<high&&a[high]>=pivoitkey)high--;
		a[low]=a[high];
		while(low<high&&a[low]<pivoitkey)low++;
		a[high]=a[low];
	}
	a[low]=pivoitkey;
	return low;
}

void sorta(int a[],int n)
{
	int pivotindex=-1;
	int low=0;
	int high=n-1;
	while(low<high)
	{
		pivotindex=Partition(a,low,high);
		if(pivotindex<n/2)
		    low=++pivotindex;
		else if(pivotindex==n/2)
		   break;
		else
		    high=--pivotindex;
	}
}



int main()
{
	int n;
	
	while(1)
	{
	    int flag=1,flag2=1;
	    cin>>n;
	    if(!n)
	    break;
		int *a;
	a=new int[n];
	for(int i=0;i<n;i++)
	   cin>>a[i];
	sorta(a,n);
	for(int i=0;i<n/2;i++)
	{
		if(flag)
		{
			cout<<a[i];
			flag=0;
		}
		else
		cout<<" "<<a[i];
	  
	}
	    cout<<endl;
	for(int i=n/2;i<n;i++)
	{
		if(flag2)
		{
			cout<<a[i];
			flag2=0;
		}
		else
		cout<<" "<<a[i];
	  
    }
	  cout<<endl;

	}
		return 0;
}

最后

以上就是默默白猫为你收集整理的数据结构实验一，第37题：数组的分割的全部内容，希望文章能够帮你解决数据结构实验一，第37题：数组的分割所遇到的程序开发问题。

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