程序填空题：求解一个整数数组划分为两个子数组的问题（分治法）
已知由n(n≥2)个正整数构成的集合A＝{$$a_k$$}(0≤k
```c++
#include
#include
#include
#include
#define N 1000
using namespace std;
int Partition(int a[],int low,int high)
{ int i=low,j=high;
int pivot;
pivot=a[low];
while(i {
while(i=pivot) --j;
a[i]=a[j];
while(i a[j]=a[i];
}
a[i]=pivot;
return i;
}
int solve(int a[],int n)
{ int low=0,high=n-1;
bool flag=true;
while(flag)
{
int i=Partition(a,low,high);
if(@@[i==n/2-1](2))
flag=false;
else if(@@[i low=i+1;
else
@@[ high=i-1](2);
}
int s1=0,s2=0;
for(int i=0;i @@[s1+=a[i]](2);
for(int j=n/2;j @@[s2+=a[j]](2);
return s2-s1;
}
int main()
{
int a[N],n;
cin>>n;
for(int i=0;i cin>>a[i];
cout< return 0;
}
```
### 输入格式:
第一行输入集合中元素个数n，第二行输入n个集合元素。
```in
9
1 3 5 7 9 2 4 6 8
```
### 输出格式:
输出|S1-S2|。
```out
25
```
答案：
第1空：i==n/2-1
第2空：i
第3空： high=i-1
第4空：s1+=a[i]
第5空：s2+=a[j]
```c++
#include
#include
#include
#include
#define N 1000
using namespace std;
int Partition(int a[],int low,int high)
{ int i=low,j=high;
int pivot;
pivot=a[low];
while(i
while(i
a[i]=a[j];
while(i
}
a[i]=pivot;
return i;
}
int solve(int a[],int n)
{ int low=0,high=n-1;
bool flag=true;
while(flag)
{
int i=Partition(a,low,high);
if(@@[i==n/2-1](2))
flag=false;
else if(@@[i
else
@@[ high=i-1](2);
}
int s1=0,s2=0;
for(int i=0;i
for(int j=n/2;j
return s2-s1;
}
int main()
{
int a[N],n;
cin>>n;
for(int i=0;i
cout<
}
```
### 输入格式:
第一行输入集合中元素个数n，第二行输入n个集合元素。
```in
9
1 3 5 7 9 2 4 6 8
```
### 输出格式:
输出|S1-S2|。
```out
25
```
答案：
第1空：i==n/2-1
第2空：i
第3空： high=i-1
第4空：s1+=a[i]
第5空：s2+=a[j]
