【每日一题】组队竞赛（贪心、排序）

桃扇骨 2022-12-23 14:24 128阅读 0赞

**题目来源**  
牛客网  
链接：[组队竞赛][Link 1]

**题目描述**  
牛牛举办了一次编程比赛,参加比赛的有3\*n个选手,每个选手都有一个水平值a\_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。  
例如:  
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3  
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3  
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2  
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。  
如样例所示:  
如果牛牛把6个队员划分到两个队伍。如果方案为:team1:\{1,2,5\}, team2:\{5,5,8\}, 这时候水平值总和为7，而如果方案为:team1:\{2,5,8\}, team2:\{1,5,5\}, 这时候水平值总和为10。没有比总和为10更大的方案,所以输出10。

输入描述:

> 输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)  
> 第二行包括3\*n个整数a\_i(1 ≤ a\_i ≤ 10^9),表示每个参赛选手的水平值

输出描述：

> 输出一个整数表示所有队伍的水平值总和最大值

示例：  
输入：

> 2  
> 5 2 8 5 1 5

输出

> 10

**解题思路**  
队伍的水平值等于该队伍队员中第二高水平值，为了所有队伍的水平值总和最大的解法，也就是说每个队伍的第二个值是尽可能大的值。所以实际值把最大值放到最右边，最小是放到最左边。

本题的主要思路是贪心算法，贪心算法其实很简单，就是每次选值时都选当前能看到的局部最解忧，所以这里的贪心就是保证每组的第二个值取到能选择的最大值就可以，我们每次尽量取最大，但是最大的数不可能是中位数，所以退而求其次，取每组中第二大的。举例说明：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]

**代码展示**

#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());
    		for(int i = n;i <=3 * n - 2;i += 2)
    		{
        
    			sum += a[i];
    		}
    		cout<<sum<<endl;
    	}
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/6736cc3ffd1444a4a0057dee89be789b?orderByHotValue=1&page=1&onlyReference=false
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b3c5de2019a64d0bbecf366e26bcfa05.png