//最小和最大次大组队，次小和第三大第四大组队……
//如，123456789
//下标012345678
//组队方案如下：
//189,267,345 水平值总和为8+6+4=18，是最大值
//每队队员中第二高水平值的下标：size-2*i（i=1,2,...,n）
//所有队伍的水平值总和=每队队员中第二高水平值的总和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n = 0;//声明n，表示组数
    while (cin >> n)//输入n
    {
        vector<int> a;//存放每个选手的水平值
        a.resize(3 * n);//扩容
        for (int i = 0; i < 3 * n; ++i)
        {
            cin >> a[i];//输入每个选手的水平值
        }
        sort(a.begin(), a.end());//给选手的水平值排序
        long long sum = 0;//声明sum，表示总和，值可能很大，用long long类型
        for (int i = 1; i <= n; ++i)
        {
            sum += a[a.size() - 2 * i];//sum累加
        }
        cout << sum << endl;//输出sum
    }
    return 0;
}

#include <iostream>
#include<algorithm>
using namespace std;
const int M=300003;
int n;
int a[M];
int main() {
    cin>>n;
    for(int i=0;i<3*n;i++)
      cin>>a[i];
    sort(a,a+3*n);
    long long ans=0;
    for(int i=3*n-2;i>=n;i-=2)
       ans+=a[i];
    cout<<ans<<endl;

    return 0;
}
// 64 位输出请用 printf(\"%lld\")

分析：将所有数存入arr数组中，先将数组进行排序(从小到大),每次都取数组中最小的一个、最大的一个和次大的一个，这样可以保证每次分组中拿到最大的可能的数

import java.util.Arrays;
import java.util.Scanner;

public class demo1 {
    //组队竞赛
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[3 * n];
        for(int i = 0; i < 3 * n; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
      // sum 的值可能会很大,所以用 Long 类型
        long sum = 0;

        for(int i = 0; i < n; i++) {
            sum += arr[arr.length - 2 * (i + 1)];
        }

        System.out.println(sum);
    }
}

组队竞赛

分析：将所有数存入arr数组中，竞赛时分组要使得所有组的中位数之和最大，可以先将数组进行排序(从小到大)
每次都取数组中最小的一个、最大的一个和次大的一个，这样可以保证每次分组中拿到最大的可能的数

方法一：

如：1 2 3 4 5 6 7 8 9
分组：189 267 345
则中位数最大和为 8+6+4=18
计算这几个数的下标公式：arr.length() - 2 * (i + 1)

代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入组数
        int n = sc.nextInt();
        //存储所有数据的数组
        int[] arr = new int[3 * n];
        //输入所有队员的水平值
        for(int i = 0; i < 3 * n; i++) {
            arr[i] = sc.nextInt();
        }
        //将数组进行排序
        Arrays.sort(arr);
        //存储最大水平和
        long sum = 0;
        //后 2/3 个数字的奇数位的和
        //根据公式计算最大水平和
        for(int i = 0; i < n; i++) {
            sum += arr[3 * n - 2 * (i + 1)];
        }
        //输出结果
        System.out.println(sum);
    }
}

方法二：

还有一种解法就是我没发现取的数就是排序后数组中后 2/3 的数据中从最小的一个开始依次跳一个的所有数之和
即：后 2/3 个数中所有位置为奇数的数
如：1 2 3 4 5 6 7 8 9
456789中：4+6+8=18

代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入组数
        int n = sc.nextInt();
        //存储所有数据的数组
        int[] arr = new int[3 * n];
        //输入所有队员的水平值
        for(int i = 0; i < 3 * n; i++) {
            arr[i] = sc.nextInt();
        }
        //将数组进行排序
        Arrays.sort(arr);
        //存储最大水平和
        long sum = 0;
        //后 2/3 个数字的奇数位的和
        for (int i = n; i < 3 * n; i += 2) {
            sum += arr[i];
        }
        //输出结果
        System.out.println(sum);
    }
}

public class Main1 {
    //保证每组的第二个值取到能选择的最大值就可以，
    // 我们每次尽量取最大，但是最大的数不可能是中位数，
    // 所以退而求其次,取每组中第二大的
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            long[] array = new long[3 * n];
            for (int i = 0; i < (3 * n); i++) {
                array[i] = scanner.nextLong();
            }
            Arrays.sort(array);
            long sum = 0;
            for (int i = 0; i < n; i++) {
                sum += array[array.length - (2 * (i + 1))];
            }
            System.out.println(sum);
        }
    }
}

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

int main()
{
    vector<int> v;
    long long nums;
    cin >> nums;
    v.reserve(3 * nums);
    for (size_t i = 0; i < 3 * nums; ++i)
    {
        int t;
        cin >> t;
        v.push_back(t);
    }
    sort(v.begin(), v.end());//排序
    long long tmp = 0, j = 0;
    for (int i = (3 * nums) - 2; i >= 0; i -= 2) //1 2 5 5 7 8，每次取 7 5 即可
    {
        if (j < nums)
        {
            tmp += v[i];
            ++j;
        }
        else
            break;
    }
    cout << tmp << endl;
    return 0;
}

贪心算法

既然不能选最大，我们就选第二大，将数组排个序，然后获取下标为 n, n+2, n+4,...,3n-2 的元素并求和好了
这样就获取到所有队伍的水平值总和最大值.

也可以这么理解
我们看测试用例
5 2 8 5 1 5
我们将其排序
1 2 5 5 5 8
不妨令 1 5 5 为一个组合
2 5 8 作为另一个组合
为什么要这么划分呢？
既然队伍的平均水平是队伍里第二水平的和
这样的话，我们让队伍的最小的元素就取排序后数组中的前n-1(数组下标从0开始)个元素好了
接下来的问题就是剩下的2n个元素怎么划分的问题了，我们假设这样分：
从n-2n-1的作为队伍的第二，但是这样一来，我们得到的和一定不是最大值，我们这样考虑，假如，n和n+1一组，n+2和n+3一组，这样每组的第二分别是 n, n+2, n+4,...,3n-2，显然n+1 < n+2, n+2 < n+4, n+3 < n+6, 2n < 3n-2.
这就是我们要的最大的结果呀

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define DEBUG 0

int main(void)
{
    std::vector<int> array(300003, 0);
    int n = 0;
    int i = 0;
    long long sum = 0;
    while((std::cin >> n) && ((n >= 1) && (n <= 100000)))
    {
#if DEBUG
        std::cout << "[DEBUG] n = " << n << std::endl;
#endif
        for(i = 0; i < 3*n; ++i)
        {
            std::cin >> array[i];
        }
#if DEBUG
        std::cout << "[DEBUG] before sort, array = ";
        for(i = 0; i < 3*n; ++i)
        {
            std::cout << array[i] << " ";
        }
        std::cout << std::endl;
#endif

        std::sort(array.begin(), array.begin() + 3*n);

#if DEBUG
        std::cout << "[DEBUG] after sort, array = ";
        for(i = 0; i < 3*n; ++i)
        {
            std::cout << array[i] << " ";
        }
        std::cout << std::endl;
#endif
        for(i = n; i <= 3*n -2; i = i+2)
        {
#if DEBUG 
            std::cout << "[DEBUG] array[" << i << "] = " << array[i] << std::endl;
#endif
            sum += array[i];
        }

        std::cout << sum << std::endl;
        sum = 0;
        array.clear();
#if DEBUG
        std::cout << "[DEBUG] array.capacity() = " << array.capacity() << std::endl;
#endif
    }

    return 0;
}