48天强训 Day1 JavaOj

48天强训 & Day1 & JavaOj

1. 编程题1 - 组队竞赛

组队竞赛_牛客笔试题_牛客网 (nowcoder.com)

在这里插入图片描述

1.1 读题

在这里插入图片描述

1.2 算法思想基础

我们应该尽量的让每一个队伍的中间值都最大化~
我们应该尽量的让每一个队伍的最小值都足够小~
前33%的不应该都作为每个队伍的最大值~

接下来我将讲解每个位置应该如何选组员~
- 但是这里我要说一个前提
- 首先，我们需要把所有人进行一个排序~
- 分为前三分之一，中三分之一，后三分之一
- 后三分之一为整体水平排名靠后的~

1.2.1 后三分之一

我们要想让一个队伍的最小值足够小
那么我们可以让那么就选整体水平的后三分之一
- 事实也是如此~

证明：（反证法）

首先：

在这里插入图片描述

其次：

在这里插入图片描述

得出结论：

在这里插入图片描述

也就是说，为了让组队水平最大化，我们应该让每个队伍的最小值，要在整体的后三分之一里去选~
并且这么选都可以，因为最大值和中间值都会比最小值大，并且队伍的水平不受最小值影响~

1.2.2 前三分之二

我们确定了每个队伍的最小值后，紧接着就要确定一个一个的队伍了~
- 切记，并不能让前三分之一的人都作为每个队伍的最大值，这样非常影响总体水平~
- 原理跟刚才差不多，可以用反证法证明~

在这里插入图片描述

其实这样排是有可能做对的
但是，肯定是有漏洞的~

在这里插入图片描述

而正确的思想是，一个一个队伍的去确定，每次确定都让这个队伍水平最大化~

在这里插入图片描述

对于第二个队伍

在这里插入图片描述

以此类推~

在这里插入图片描述

所以，最大水平组队方式就是这样的
水平总和最大值为：
- 假设有n个队伍
- 所有人从大到小排为 a_3n
- 水平总和值为S_n
- 则S_nmax = a₂ + a₄ + a₆ + ······ + a_2n

1.3 代码设计

n为队伍的个数
那么我们只需要知道前2n名
- topK问题
- 用优先级队列 - 堆
- 前k大，用小根堆
- 每次去梢（poll）,就是去掉最小值
- 这里就相当于去掉a_2n、a_2n-1 ······
按照上面的算法，我们可以从a_2n + a_2n-2 + ······ + a₄ + a₂
- 即从后往前加

当然也可以直接用各种排序方式去排序，然后按照下标依次相加~

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);
        }
	}
}