Day 007：PAT训练--1108 Finding Average (20 分)

话不多说：

该题要求将给定的所有数分为两类，其中这两类的个数差距最小，且这两类分别的和差距最大。

可以发现，针对第一个要求，个数差距最小，当给定个数为偶数时，二分即差距为0，最小；若给定个数为奇数时，差距为1时最小。

针对第二个要求：则将所有给定的数从小到大排列，将前半部分给那个和小些的集合，其余给那个和大的集合，这样做和差距会最大。

以此思路编写代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn = 101000;

long long ans[maxn] = {0};

bool cmp(long long a, long long b){

    if(a != b)

        return a < b;

}

int main(){

    int n;

    long long mx = 0, mn = 0;

    cin >> n;

    fill(ans, ans + maxn, 0);

    for(int i = 0; i < n; i++){

        cin >> ans[i];

    }

    sort(ans, ans + n, cmp);

    if(n % 2 == 0){

        for(int j = 0; j < n / 2; j++){

            mn += ans[j];

        }

        for(int k = n / 2; k < n; k++){

            mx += ans[k];

        }

        cout << "0" << ' ' << mx - mn;

    }else{

        for(int l = 0; l < (n - 1) / 2; l++){

            mn += ans[l];

        }

        for(int m = (n - 1) / 2; m < n; m++){

            mx += ans[m];

        }

        cout << "1" << ' ' << mx - mn;

    }

    return 0;

}

看似没问题，但是这样提交第二个测试点会显示段错误，研究后发现关于cmp的返回判断条件有误，去除if(a != b)该条件后则AC。

研究后发现，具体原因还不是很懂，但是用cmp一定要保证严格弱排序的规则，一定要保证所有情况都有返回bool的值。（刚才那种情况，若a == b时，就没有返回值）。

严格是说在判断的时候会用"<"，而不是"<="，弱排序是因为，一旦"<"成立便认为存在"<"关系，返回ture，而忽略了"="关系和">"区别，把它们归结为false。

改进后的代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn = 101000;

long long ans[maxn] = {0};

bool cmp(long long a, long long b){// 去掉cmp判断条件段错误消失了

    return a < b;

}

int main(){

    int n;

    long long mx = 0, mn = 0;

    cin >> n;

    fill(ans, ans + maxn, 0);

    for(int i = 0; i < n; i++){

        cin >> ans[i];

    }

    sort(ans, ans + n, cmp);

    if(n % 2 == 0){

        for(int j = 0; j < n / 2; j++){

            mn += ans[j];

        }

        for(int k = n / 2; k < n; k++){

            mx += ans[k];

        }

        cout << "0" << ' ' << mx - mn;

    }else{

        for(int l = 0; l < (n - 1) / 2; l++){

            mn += ans[l];

        }

        for(int m = (n - 1) / 2; m < n; m++){

            mx += ans[m];

        }

        cout << "1" << ' ' << mx - mn;

    }

    return 0;

}

总而言之，在PAT中，若题目没有保证所有需要排序的值都是两两不同的（比如这道题），则尽量不要用if(a != b)这样的判断条件，一定要保证cmp函数在所有情况都有返回值！！！！！否则会出现段错误！！！！！

Over~希望大家回去也能好好练习，最近我感觉水平有提升了，还有，那两天没更新，我每天也有练习哦。（当然我最希望没人能看见嘿嘿）

巴特西

Day 007：PAT训练--1108 Finding Average (20 分)

最新文章

热门文章