【错题集-编程题】组队竞赛（排序 + 贪心）

牛客对应题目链接：组队竞赛_牛客笔试题_牛客网 (nowcoder.com) 

一、分析题目

运用 贪心 思想：

• 先将数组排好序。
• 总和最大 -> 每个小组的分数尽可能大。
• 最大的数拿不到，只能退而求其次拿到倒数第⼆个⼈的分数，再补上一个小的数来消耗。（消耗一个最大和一个最小的数）

二、代码

1、未看题解之前AC的代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long LL;

const int N=1e5+10;
int a[3*N];

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<3*n; i++)
        cin >> a[i];
    sort(a, a+3*n);
    vector<int> dp(n);
    int k=3*n-2;
    for(int i=0; i<n; i++)
    {
        dp[i]=a[k];
        k-=2;
    }
    LL sum=0;
    for(int i=0; i<n; i++)
        sum+=dp[i];
    cout << sum << endl;
    return 0;
}

2、值得学习的代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
LL arr[N * 3];

int main()
{
    cin >> n;
    for(int i = 0; i < 3 * n; i++) cin >> arr[i];
    sort(arr, arr + 3 * n);

    int pos = 3 * n - 2, count = 1;
    LL ret = 0;
    while(count++ <= n)
    {
        ret += arr[pos];
        pos -= 2;
    }

    cout << ret << endl;

    return 0;
}

三、反思与改进

这道题刚开始没什么思路，后面按照题意去模拟思考就可以知道该如何拿到第二大的数了。其次，得注意这道题的输入数据是有 3*n 个的，所以在给数组开大小和排序，以及后面 k 的取值都需要从 3*n 开始考虑。再者，就是要注意这道题目所给的数据范围，因为是求和，所以可能会超出数据范围，那么这里就得用到 long long 来存储数据。