1.问题描述
令S为一个n个正整数的集合，n为偶数。请设计一个有效算法将S分成两个子集S1和S2，使每个子集中含有n/2个元素，而且S1中所有元素的和与S2中所有元素的和的差最大。这个算法的时间复杂性是什么？
2. 具体要求
输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。
输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开。
限于平台，输出的两个新整数集合中的数要求按照从小到大排序后输出。这对算法时间复杂性有一定影响。
3. 测试数据
输入：
2
22
68 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12
26
28 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2
输出：
2 3 4 6 12 13 16 17 20 21 25
29 34 37 39 43 51 57 68 76 78 95
2 2 3 7 9 14 24 26 28 29 32 37 37
42 47 48 51 51 52 59 61 62 65 73 78 95
4. 设计与实现的提示
本题可以有多种方法。算法时间复杂性是选取算法的重要依据。限于平台，输出的两个新整数集合要求按照从小到大排序后输出。这对算法时间复杂性可能有所影响。
5、程序实现（java）
1
import java.io.*;
2public class Intrl2
3
{
4
public static void main(String[] args) throws Exception
5
{
6 Intrl2 yeyunce=new Intrl2();
7 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
8 System.out.println("请输入测试例个数:");
9 String str=br.readLine();
10 int m=Integer.parseInt(str);
11 yeyunce.Test(m);
12
}
13
14 public static int SPLIT(int[] A,int low,int high)
15 {
16 int w;
17 int i=low;
18 int x=A[low];
19 for(int j=low+1;j<=high;j++)
20 {
21 if(A[j]<=x)
22 {
23 i=i+1;
24
25 if(i!=j)
26 {
27 int a;
28 a=A[i];
29 A[i]=A[j];
30 A[j]=a;
31 }
32 }
33 }
34 int a2;
35 a2=A[low];
36 A[low]=A[i];
37 A[i]=a2;
38 w=i;
39 return w;
40 }
41
42 public static void quicksort(int[] A,int low,int high)
43 {
44 int w;
45 if(low<high)
46 {
47 w=SPLIT(A,low,high);
48 quicksort(A,low,w-1);
49 quicksort(A,w+1,high);
50 }
51 }
52
53 public void Test(int m)
54 {
55 String[][] ss=new String[m][2];
56 for(int i=0;i<m;i++)
57 {
58 try
59 {
60 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
61 System.out.println("总测试例个数为"+m+",现请输入第"+(i+1)+"个用例数组的元素个数，并在下一行列出:");
62 String str=br.readLine();
63 int d=Integer.parseInt(str);
64 String str2=br.readLine();
65 String[] str3=str2.split(" ");
66 int[] ii=new int[d];
67 for(int j=0;j<d;j++)
68 {
69 ii[j]=Integer.parseInt(str3[j]);
70 }
71 quicksort(ii,0,d-1);
72 String sf1="";
73 String sf2="";
74 for(int f1=0;f1<d/2;f1++)
75 {
76 sf1+=ii[f1]+" ";
77 }
78 for(int f2=d/2;f2<d;f2++)
79 {
80 sf2+=ii[f2]+" ";
81 }
82 ss[i][0]=sf1;
83 ss[i][1]=sf2;
84 }
85 catch(IOException e)
86 {
87 System.out.println(e);
88 }
89 }
90 for(int i=0;i<m;i++)
91 {
92 System.out.println();
93 for(int j=0;j<2;j++)
94 {
95 System.out.println(ss[i][j]);
96 }
97 }
98 }
99
}
6、运行结果
