組隊競賽-Java-牛客模拟三

在做筆試中算法題目時，了解題意和解題思路是非常關鍵。其實此題目知道了解題思路後是非常簡單的。

package 模拟三;

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

/**
 * 題目描述：牛牛舉辦了一次程式設計比賽,參加比賽的有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
 * 
 * @author 崔洪振367
 * @version 建立時間：2017年5月23日 下午8:04:11
 * 解題思路：在測試中，我原來的解法是将數組排序a[0]--a[3*n-1]，然後從a[1]開始每個兩個數求和。這樣做不能全部AC。
 * 正确的解題思路如下代碼：也是先排序數組，将0----(n-1)的數視為每個子數組的最小值。然後，從3 * n - 2開始，每隔兩個數求和。
 * 把這些值作為子數組的第二個值，也就是這個隊伍的水準總和。
 */
public class Q2017_6組隊競賽 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			sc.nextLine();
			int[] a = new int[3 * n];
			for (int i = 0; i < 3 * n; i++) {
				a[i] = sc.nextInt();
			}

			Arrays.sort(a);// 排序
			long sum = 0;
			// 交替擷取相隔2的值,就是說将3*n-2,3*n-4,3*n-6,作為每一組的中間值
			for (int i = 3 * n - 2; i >= n; i -= 2) {
				sum += a[i];
			}
			System.out.println(sum);
		}
		sc.close();
	}

}