48天强训 & Day1 & JavaOj
1. 编程题1 - 组队竞赛
组队竞赛_牛客笔试题_牛客网 (nowcoder.com)
1.1 读题
1.2 算法思想基础
我们应该尽量的让每一个队伍的中间值都最大化~
我们应该尽量的让每一个队伍的最小值都足够小~
前33%的不应该都作为每个队伍的最大值~
接下来我将讲解每个位置应该如何选组员~
但是这里我要说一个前提
首先，我们需要把所有人进行一个排序~
分为前三分之一，中三分之一，后三分之一
后三分之一为整体水平排名靠后的~
1.2.1 后三分之一
我们要想让一个队伍的最小值足够小
那么我们可以让那么就选整体水平的后三分之一
事实也是如此~
证明：（反证法）
首先：
其次：
得出结论：
也就是说，为了让组队水平最大化，我们应该让每个队伍的最小值，要在整体的后三分之一里去选~
并且这么选都可以，因为最大值和中间值都会比最小值大，并且队伍的水平不受最小值影响~
1.2.2 前三分之二
我们确定了每个队伍的最小值后，紧接着就要确定一个一个的队伍了~
切记，并不能让前三分之一的人都作为每个队伍的最大值，这样非常影响总体水平~
原理跟刚才差不多，可以用反证法证明~
其实这样排是有可能做对的
但是，肯定是有漏洞的~
而正确的思想是，一个一个队伍的去确定，每次确定都让这个队伍水平最大化~
对于第二个队伍
以此类推~
所以，最大水平组队方式就是这样的
水平总和最大值为：
假设有n个队伍
所有人从大到小排为 a3n
水平总和值为Sn
则Snmax = a2 + a4 + a6 + ······ + a2n
1.3 代码设计
n为队伍的个数
那么我们只需要知道前2n名
topK问题
用优先级队列 - 堆
前k大，用小根堆
每次去梢（poll）,就是去掉最小值
这里就相当于去掉a2n、a2n-1 ······
按照上面的算法，我们可以从a2n + a2n-2 + ······ + a4 + a2
即从后往前加
当然也可以直接用各种排序方式去排序，然后按照下标依次相加~
public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNextInt()) { int number = scanner.nextInt(); PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for (int i = 0; i < number * 3; i++) { int value = scanner.nextInt(); if(i < 2 * number) { priorityQueue.offer(value); }else { if(value > priorityQueue.peek()) { priorityQueue.poll(); priorityQueue.offer(value); } } } long result = 0; for (int i = 0; i < number; i++) { result += priorityQueue.poll(); priorityQueue.poll(); } System.out.println(result); } } }
解析：
1. 3. 测试
