牛客: 組隊競賽

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

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

int main()
{
  int n = 0;
  cin >> n;
  if (n <= 0)
    return 0;
  vector<int> v;
  v.reserve(3 * n);
  int ret = 0;
  for (int i = 0; i < 3 * n; i++)
  {
    cin >> ret;
    v.push_back(ret);
  }
  sort(v.begin(), v.end());
  long long sum = 0; // 鄙視牛客 這個還要求
  for (int i = 0; i < n; i++)
  {
    sum += v[3 * n - 2 * (i + 1)];
  }
  cout << sum;
  return 0;
}