USACO 2024 January -- Gold (Nap Sort)

USACO金奖被视为一个很有分量的学术成就。获得该奖能够显著增加进入顶级夏校/一流大学的机会，尤其是像斯坦福大学、MIT、哈佛大学等院校。不久前结束的2025/一月考试，全美仅有12名同学获得认证（名单如下）。
题目给出的信息：已知Bessie 正在尝试使用自己的排序算法对一个整数数组进行排序。有一堆共 N （1≤N≤2⋅10^5 ）个整数 a1,a2,…,aN （1≤ai≤10^11 ），Bessie将会按排序顺序将这些数放入一个单独的数组中。反复查找这堆数中的最小数，将其删除，同时将其添加到数组的末尾。Bessie 在 p 个数的堆中找到最小数需要花费 p 秒。 FJ命令了农场中其他一些奶牛帮助 Bessie 完成任务，奶牛很懒，然而 Bessie 利用了这一点，将整数分成两堆：Bessie 堆和助手堆。对于 Bessie 堆中的每个整数，会正常执行算法。对于助手堆中的每个整数，将其分配给不同的助手奶牛。FJ 有一个很大的农场，所以 Bessie 可以找来任意多的助手奶牛。如果助手收到整数 ai ，Bessie 会指示该牛小睡 ai 秒，并在醒来时立即将该整数添加到数组末尾。如果 Bessie 和一个助手同时向数组添加整数，Bessie 的整数将优先被添加。如果多个助手被分配了相同的整数，会同时将多个该整数添加到数组中。 使得最终得到的数组是排序的，问排序数组所需要的最小时间？输入：T         N         a1,a2,…,aN输出：排序数组所需要的最小时间时间复杂度： O(n) 或 O(nlogn)分析：根据题意，最终得到的数组是排序的，故我们需首先对于N个数字进行从小到大的排序。如果Bessie把所有数字分配给其他奶牛，则所需的时间即为N个数字中的最大值（amax）。如果Bessie分担部分工作，则工作中需要包括amax，否则，其所做为无用功，还不如不做。如果Bessie分配到的任务数为x，那么其共需x(x+1)/2秒来完成其任务。为确保Bessie可以承担amax的排序，则对于可能分配到的任务数（x）进行检测，即满足条件：index + 1 - # = N - x。这里，index指排序后的a1, a2, … , aN中数字的所在位置；#指x个数中在helpers最后数字前的总数。另外，因最终目的是获得最小可能时间，即min（x(x+1)/2，amax），满足条件的x值越小，越接近目标，故我们可以利用二分搜索算法（binary search algorithm）来找出这个x值。具体细节参照��的程序设计。举一例来说明，Input：1 62 5 100 1 4 5
首先排序后的数字为1 2 4 5 5 100，利用二分搜索算法（binary search algorithm），首先测试Bessie分配到的任务数为3，则其工作的时间分别为第3秒，第5秒，第6秒，helpers分配到1，2，5任务。故满足index + 1 - # = 4 + 1 - 2 = 6 - 3 = 3。任务6秒完成。再试更小的任务数2，则其工作的时间分别为第2秒，第3秒，helpers分配到1，5，5，100任务。无法满足条件。所以答案为6秒。