PAT甲级1113.

目录

A1113

题目

样例

样例1

输入:

10
23 8 10 99 46 2333 46 1 666 555

输出:

0 3611

样例2

输入:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出:

1 9359

思路和坑点

　　思路:
　　此题其实就是对数组进行对半划分，小的部分在一侧，大的部分在另一侧，如果是偶数个元素，则对半划分，如果是奇数个元素，将位于中间的那个元素归在数值较大的部分。最后，对两部分进行累加求和并输出结果即可。可以直接对整个数组进行排序然后统计，也可以采用快排划分的思路进行划分（不需要全部排序），只要中间位置的元素划分划分，就可以满足题目要求的划分条件。

AC代码（暴力解法）

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);         
    vector<int> v(n);
    for(int i=0;i<n;i++)            //读入数据
        scanf("%d",&v[i]);
    //根据题意确定n1和n2，
    int n1=n/2;                     //由题意可知，n1、n2需要尽可能的个数上接近；S1和S2的插值需要尽可能的大，所以也就是排序后的前一半和后一半
    int n2=n-n1;                    //由于元素个数奇数个和偶数个的情况不同，偶数个则对半分，奇数个（从小到大排序），后半部分比前部分多一个元素
    sort(v.begin(),v.end());        //从小到大排序
    int s1=0,s2=0;                  //统计两部分的和
    for(int i=0;i<n1;i++) s1+=v[i];
    for(int i=n1;i<n;i++) s2+=v[i];
    printf("%d %d",n2-n1,s2-s1);    //按照要求进行输出
    return 0;    
}

AC代码（划分解法）

　　其他同学提供的划分算法，顺利AC，划分方法的区别在此不做说明。

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif   
    int n,n1,n2;
    scanf("%d",&n);         
    int *v=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)            //读入数据
        scanf("%d",&v[i]);
    int low_tmp=0,high_tmp=n,tmp;
    while(1){                       //快排划分方法进行划分
        int low=low_tmp,high=high_tmp;
        tmp=v[low];
        while(1){
            while(v[--high]>tmp) if(high==low_tmp) break;
            while(v[++low]<tmp) if(low==high_tmp) break;
            if(low>=high) break;
            swap(v[low],v[high]);
        }
        swap(v[low_tmp],v[high]);
        if(high==n/2) break;         //如果完成划分则停止
        else if(high<n/2) low_tmp=++high;
        else               high_tmp=high;
    }
    n1=n/2;
    n2=n-n1;                        //由于元素个数奇数个和偶数个的情况不同，偶数个则对半分，奇数个（从小到大排序），后半部分比前部分多一个元素
    int s1=0,s2=0;                  //统计两部分的和
    for(int i=0;i<n1;i++) s1+=v[i];
    for(int i=n1;i<n;i++) s2+=v[i];
    printf("%d %d",n2-n1,s2-s1);    //按照要求进行输出
    return 0;    
}

未AC代码（划分解法）

　　此方法测试点3超时，算法逻辑没有错误，但是应对超长有序（和划分的排序规则相同的有序）序列时耗时过长导致程序超时。

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n,n1,n2;
    scanf("%d",&n);         
    int *v=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)            //读入数据
        scanf("%d",&v[i]);
    int low=0,high=n-1,tmp;
    int low_tmp=low,high_tmp=high;  //更新记录上一次划分的边界
    while(1){                       //快排划分方法进行划分
        tmp=v[low];
        while(low<high){
            while(low<high&&v[high]>=tmp) high--;
            v[low]=v[high];
            while(low<high&&v[low]<=tmp) low++;
            v[high]=v[low];
        }
        v[low]=tmp;
        if(low==n/2) break;         //如果完成划分则停止，如果未完成则继续对包含了中间值的哪个部分进行划分
        else if(low<n/2) { low_tmp=++low,high=high_tmp; }
        else             { low=low_tmp,high_tmp=--high; }
    }
    n1=n/2;
    n2=n-n1;                        //由于元素个数奇数个和偶数个的情况不同，偶数个则对半分，奇数个（从小到大排序），后半部分比前部分多一个元素
    int s1=0,s2=0;                  //统计两部分的和
    for(int i=0;i<n1;i++) s1+=v[i];
    for(int i=n1;i<n;i++) s2+=v[i];
    printf("%d %d",n2-n1,s2-s1);    //按照要求进行输出
    return 0;    
}
/*
处理数据超时的情况：超大有序序列，在划分是时间花费比较多，比如
100000
全是1
*/