题:组队竞赛-求最大水平值总和

    xiaoxiao2022-07-03  95

    题目:求水平值总和

    题目分析:

    队伍的水平值等于该队伍队员中第二高水平值,也就是说每个队伍 的第二个值是尽可能大。


    解题思路:

    --->可以把每个组数据从小到大排序,取第二大的数。把所有第二大的数据全部加起来,就是最大水平值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():快排函数的使用

    题目知识:

    贪心算法,就是每次选值时都选当前能看到的局部最优解,但是这个题目只是最优解变成了次大的数。

     

    最新回复(0)