【Java版oj】day01组队竞赛

男娘i 2024-03-31 12:01 86阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> 链接：[组队竞赛\_牛客笔试题\_牛客网][Link 1]  
> 来源：牛客网
> 
> \[编程题\]组队竞赛
> 
>  *  热度指数：7260 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
>  *  算法知识视频讲解 
> 
> 牛牛举办了一次编程比赛,参加比赛的有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),表示每个参赛选手的水平值
> 
> **输出描述:**
> 
>     输出一个整数表示所有队伍的水平值总和最大值.
> 
> 示例1
> 
> ### 输入 ###
> 
>     2
>     5 2 8 5 1 5
> 
> ### 输出 ###
> 
>     10

> ## 二、问题分析 ##
> 
> 每三个数为一组，尽可能的使得中间值最大。首先现将数组排序，数组长度必然为3的倍数。每次最小值从\[0,n)中取值，最大和次大在\[n,3n)中取值，可以很容易得出次大值从n开始取值，每次步长为2。
> 
> ![2e4e4db9e0b940a99c87d144ec029486.png][]

> ## 三、完整代码 ##
> 
>     import java.util.*;
>     public class Main1 {
>         public static void main(String[] args) {
>             List<Long> list=new ArrayList<>();
>             Scanner sc = new Scanner(System.in);
>             int n=sc.nextInt();
>             long ans=0;
>             long a_i=0;
>             for(int i=0;i<3*n;i++){
>                 a_i=sc.nextLong();
>                 list.add(a_i);
>             }
>             Collections.sort(list);
>             for(int j=n;j<3*n;j=j+2){
>                 ans+=list.get(j);
>             }
>             System.out.println(ans);
>         }
>     }
> 
> ![862178f5da6d4020af7d8a5acbaf125b.png][]

--------------------

![c270e5b096ea4dd69e0c7055e9ceb616.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/6736cc3ffd1444a4a0057dee89be789b?orderByHotValue=1&page=1&onlyReference=false
[2e4e4db9e0b940a99c87d144ec029486.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/74eeedd0a22042d1a1afdfebb5f08290.png
[862178f5da6d4020af7d8a5acbaf125b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/31f3b7f350084dc7b7ee2486577cfcd4.png
[c270e5b096ea4dd69e0c7055e9ceb616.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f81f5aca582149e7b90ffd42d18bba09.png