🎉🎉🎉点进来你就是我的人了
博主主页:🙈🙈🙈戳一戳,欢迎大佬指点!
人生格言:当你的才华撑不起你的野心的时候,你就应该静下心来学习!欢迎志同道合的朋友一起加油喔🦾🦾🦾
目标梦想:进大厂,立志成为一个牛掰的Java程序猿,虽然现在还是一个🐒嘿嘿
谢谢你这么帅气美丽还给我点赞!比个心
链接:组队竞赛__牛客网
来源:牛客网
牛牛举办了一次编程比赛,参加比赛的有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
解题思路:
其实这题大家没有必要想的那么复杂,一共n组队伍,每组队伍3个人,我们要找的就是每组队伍中排名第二高的数,既然如此那么n组队伍中n个最小的值我们必然不会选到,可以直接剔除.
剔除掉n个最小的值那么问题就简单了,那么这个剩下的这组数据是不是一半是中间值一半是最高值了!
其实说到这里我都感觉我在说废话,主要怕大家读不懂题意
每个队伍里只有三个人,最差的我们不会选,最高的我们也不会选,剔除n个最小值之后找中间值,我们有两种做法,一种是从前往后找,一种是从后往前找!
从前往后找:首先将数组排好序,注意下标是从0开始,剔除前面n个数(也就是下标0~n的位置),那么第n个位置就是我们要找第一个中间,后面依次加2找下一个中间值,依次累加求和.
从后往前找:首先将数组排好序,此时我们从length-2的位置开始(length-1是最后一个下标的位置),那么lengh-2就是我们要找的第一个中间值的位置,后面依次-2找下一个中间值,依次累加求和,到下标n的位置停止(i>=n).
为什么我们这里要+2或者-2呢?
因为剔除完n个最小的值以后,中间值和最高值就对半分了!
下面自己画的草图帮助你大家更好的理解(此处是从后往前举例)
代码实现 :
import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt();int[] array = new int[3 * n];for (int i = 0; i < array.length; i++) {array[i] = in.nextInt();}Arrays.sort(array);long sum = 0;for (int i = array.length - 2; i >= n; i -= 2) {sum += array[i];}System.out.println(sum);}}
}