Nap Sort

题目描述

Bessie 正在尝试使用她自己的排序算法对一个整数数组进行排序。 她有一堆 $N$ 个整数 $a_1,a_2,\dots,a_N$（$1 \leq N \leq 2\cdot 10^5$），其中 $(1 \leq a_i \leq 10^{11})$，她将把它们按升序放入一个单独的数组中。她反复执行如下操作：在她的堆中找到最小的整数，将其移除，并把它添加到数组的末尾。对于包含 $p$ 个整数的堆，Bessie 需要 $p$ 秒来找到其中的最小整数。

Farmer John 指派了农场里的其他一些奶牛来帮助 Bessie，但她们非常懒，所以 Bessie 反而利用了这一点。她将整数分成两堆：Bessie 堆与助手堆。对于 Bessie 堆中的每个整数，她照常执行她的算法。对于助手堆中的每个整数，她将其分配给一头不同的助手奶牛。Farmer John 的农场很大，所以 Bessie 可以获得任意多的助手奶牛。若某个助手收到整数 $a_i$，Bessie 会让这头奶牛先睡 $a_i$ 秒，并在醒来时立刻把该整数添加到数组末尾。若 Bessie 与某个助手在同一时刻向数组中添加整数，由于 Bessie 是领队，Bessie 的整数会先被添加。若有多头助手被分配到相同的整数，它们会在同一时刻把该整数的多个副本添加到数组中。

请帮助 Bessie 划分这些整数，使得最终得到的数组是有序的，并且完成排序所需的时间最小。

输入格式

第一行包含 $T$，表示相互独立的测试用例数量（$1\le T\le 10$）。 每个测试用例如下： 每个测试用例的第一行包含整数 $N$，表示 Bessie 数组中的整数个数。 每个测试用例的下一行包含 $a_1, a_2, \dots, a_N$，即 Bessie 要排序的整数。相同的整数可能出现多次。 保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一行，表示当 Bessie 以最优方式划分整数时，完成排序所需的最小时间。

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

6
15
5
6

提示

在第一个样例中，Bessie 可以将 $1,2$ 分配给助手，并把 $4,5,10^{11}$ 留给自己。 Time | Event -----+---------------------- 1 | Helper adds 1 2 | Helper adds 2 3 | Bessie adds 4 5 | Bessie adds 5 6 | Bessie adds 10^{11} 在第二个样例中，Bessie 能做的最好方案是全部由她自己完成排序。一个不可行的划分是：Bessie 把 $4$ 分配给助手，其余留给自己，因为 Bessie 会在助手把 $4$ 加入数组之前就把 $17$ 加入数组。 在第三个样例中，Bessie 可以把所有整数都分配给助手。 在第四个样例中，Bessie 可以将 $1,4,5$ 分配给助手，并把 $2,5,100$ 留给自己。 Time | Event -----+------------------ 1 | Helper adds 1 3 | Bessie adds 2 4 | Helper adds 4 5 | Bessie adds 5 5 | Helper adds 5 6 | Bessie adds 100 SCORING: Input 2: $N\le 16$ Inputs 3-5: $N\le 150$ Inputs 6-8: $\sum N\le 5000$ Inputs 9-11: No additional constraints. Problem credits: Suhas Nagar

标签: USACO|2024|Gold

来源

USACO|2024|Gold