48天强训 & Day1 & JavaOj

1. 编程题1 - 组队竞赛

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

1.1 读题

1.2 算法思想基础

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

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

1.2.1 后三分之一

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

证明：（反证法）

• 首先：

• 其次：

• 得出结论：

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

1.2.2 前三分之二

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

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

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

• 对于第二个队伍

• 以此类推~

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

1.3 代码设计

1. n为队伍的个数
2. 那么我们只需要知道前2n名
   • topK问题
   • 用优先级队列 - 堆
   • 前k大，用小根堆
   • 每次去梢（poll）,就是去掉最小值
   • 这里就相当于去掉a_2n、a_2n-1 ······
3. 按照上面的算法，我们可以从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);}}
}

• 解析：

1. 3. 测试