【牛客網】組隊競賽

題目描述

牛牛舉辦了一次程式設計比賽,參加比賽的有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

解題思路

【題目解析】：

隊伍的水準值等于該隊伍隊員中第二高水準值，為了所有隊伍的水準值總和最大的解法，也就是說每個隊伍 的第二個值是盡可能大的值。是以實際值把最大值放到最右邊，最小是放到最左邊。

【解題思路】：

本題的主要思路是貪心算法，貪心算法其實很簡單，就是每次選值時都選目前能看到的局部最優解，所 以這裡的貪心就是保證每組的第二個值取到能選擇的最大值就可以，我們每次盡量取最大，但是最大的 數不可能是中位數，是以退而求其次，取 每組中第二大的 排序，然後取下标為3n - 2，3n - 4 ，3n - 4… n+2，n位置的元素累加即可，相當下标為[0,n-1]的n個數 做每組的最左邊的數，剩下的2個資料兩個為一組，大的值做最右邊的數，次大的做中間值，這裡就是 把這個次大的值加起來。

例如 現在排序後 有 1 2 5 5 8 9 ，那麼取 8 和 5相加等于 13

完整代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>

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

long long Grops(int n, vector<int> v)
{
	sort(v.begin(), v.end());
	int i = n;
	long long sum = v[i];
	while (i<(3*n-2))
	{
		i += 2;
		sum += v[i];
	}
	return sum;
}
int main()
{
	int n = 0;
	while (cin >> n)
	{
		int a = 3 * n;
		vector <int> v;
		for (int i = 0; i<a; i++)
		{
			int a_i = 0;
			cin >> a_i;
			v.push_back(a_i);
		}
		cout << Grops(n, v) << endl;
	}
	system("pause");
	return 0;
}