题目:求水平值总和
题目分析:
队伍的水平值等于该队伍队员中第二高水平值,也就是说每个队伍 的第二个值是尽可能大。
解题思路:
--->可以把每个组数据从小到大排序,取第二大的数。把所有第二大的数据全部加起来,就是最大水平值zong'he
--->但是分成三个三个的一组,很麻烦,很难,可以排成一个组
--->考虑一个组之后,考虑全部排序,发现三个三个分的时候的下标的关系
--->把这些关系下标求和,就是所要求的答案
下标关系:
验证一下我们找到的关系:
这个关系是正确的。
编写代码:
#include<iostream>
#include<algorithm>
#include<vector> //容器
using namespace std;
int main() {
int n;
while (cin >> n) {
long long sum = 0;
vector<int> a; //创建容器
a.resize(3*n);
for (int i = 0; i < (3 * n); i++) {
cin >> a[i];
}
std::sort(a.begin(), a.end()); //容器进行快排的函数sort():排序
for (int i = n; i <= 3 * n - 2; i += 2) { //求和
sum += a[i];
} cout << sum << endl;
}
}
代码中的知识点:
vector:vector容器的使用std::sort():快排函数的使用
题目知识:
贪心算法,就是每次选值时都选当前能看到的局部最优解,但是这个题目只是最优解变成了次大的数。