2016年408统考就出了这个题。
可惜。。。今年考研的我可能凉了
快速排序思想划分才是满分解法。
平均时间复杂度O(n^2)
#include <iostream>
#include <algorithm>
#define MAX 100100
int ar[MAX];
int N;
using namespace std;
int partition(int le, int ri){
int pivot = ar[le];
while(le < ri){
while(le < ri && ar[ri]>=pivot){
ri--;
}
ar[le] = ar[ri];
while(le < ri&& ar[le] <= pivot){
le++;
}
ar[ri] = ar[le];
}
ar[le] = pivot;
return le;
}
void quick_partition(int low, int high){
int k = partition(low, high);
while(k+1 != N/2)
{
if(k+1 < N/2){
low = k+1;
k = partition(low, high);
}
else{
high = k-1;
k = partition(low, high);
}
}
}
int main(){
cin>>N;
for(int i = 0; i < N; i++){
scanf("%d",&ar[i]);
}
printf("%d ", N%2==1 ? 1:0);
quick_partition(0,N-1);
int sum1=0;
int sum2 = 0;
for(int i=0;i < N;i++){
if(i<N/2)
sum1 += ar[i];
else sum2 += ar[i];
}
printf("%d\n",(sum2-sum1));
return 0;