2016年408数据结构真题

//2016年真题

//这道题目的是求出|n1-n2|的最小值，也就是左右两部分的元素总个数尽可能的接近，
// 当中元素个数为偶数的时候，这个值为0，反之这个值为1，类似与AVL
//|S1-S2|的最大值也就是让左右两边 块间完全有序，让左边的元素的最大值小于右边元素的最小值
//我的想法是使用AVL树和BST树的思想以及快速排序来解决这个问题
//首先我对这个序列进行快速排序，之后根据总元素个数的奇偶性来得出|n1-n2|的最小值是0还是1
//要是总元素个数为奇数的时候，我在取这个序列的中位数的时候要判断一下中间元素放在左边还是右边使得|S1-S2|取得最大值
//在元素总个数为奇数的时候，|n1-n2|确定是1了，需要根据这个中位数分别放在左右两边而导致的两种不同的|s1-s2|结果，取绝对值最大的这种情况
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}

int sum(int a[],int low,int high){
    int sum = 0;
for (int i = low; i < high; ++i) {
        sum +=a[i];
    }
return sum;
}

void quick_sort(int a[],int low,int high){
if (low >= high)
return;
    int i = low,j = high;
    int pivot = a[i];
while (i < j){
while (i < j && a[j] > pivot)
            j--;
while (i < j && a[i] < pivot)
            i++;
        swap(a[i],a[j]);
    }
    swap(a[low],a[i]);
    quick_sort(a,low,i-1);
    quick_sort(a,i+1,high);
}

void partation(int a[],int n){
    quick_sort(a,0,n-1);
    int mid = n/2;
    int s1,s2,s_max1,s_max2;
    int n1,n2;
if (n % 2 == 0){  //如果总的元素个数是偶数
        s1 = sum(a,0,mid);
        s2 = sum(a,mid,n);
printf("|n1-n2| = 0,|s1-s2| = %d", abs(s1-s2));
    } else{
        s1 = sum(a,0,mid+1);
        s2 = sum(a,mid+1,n);
        s_max1 = abs(s1-s2);

        s1 = sum(a,0,mid);
        s2 = sum(a,mid,n);
        s_max2 = abs(s1-s2);
printf("|n1-n2| = 1,|s1-s2| = %d", s_max2 > s_max1 ? s_max2 : s_max1);
    }
}