编程题——组队竞赛

题目描述

牛牛举办了一次编程比赛，参加比赛的有3 * N个选手，每个选手都有一个水平值A_I。现在要将这些选手进行组队，一共组成Ñ个队伍，即每个队伍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。

贪心算法： 又称为贪婪算法，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

程序代码如下：

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

/*本题使用贪心算法，即保证每组的第二个值为当前最优选择
 *我们每次尽量选最大，但最大不能作为中位数，所以我们退而求次，取第二大
 *先排序：从大到小
 *再取第3n-1、3n-3、3n-5...作为每组第二个值累加起来*/
int main()
{
	int n;//用来保存组数
	while (cin >> n) //循环读取输入
	{
		long long sum = 0; //用来保存总和
		vector<int> a(3 * n);//用来保存选手水平值
		for (int i = 0; i < 3 * n; ++i)//循环读取选手水平值并保存
		{
			cin >> a[i];
		}

		sort(a.begin(),a.end());//对选手水平值从大到小排序
		for (int i = n; i <= 3*n-2; i+=2)//从大到小分组并将每组第二大的值加起来
		{
			sum += a[i];
		}
		cout << sum << endl;//输出总和
	}
	return 0;
}

程序运行结果如下：