牛客对应题目链接：组队竞赛_牛客笔试题_牛客网 (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 来存储数据。
