{"problem":{"name":"[USACO24JAN] Nap Sort G","description":{"content":"Bessie 正在尝试使用她自己的排序算法对一个整数数组进行排序。她有一堆共 $N$（$1\\le N\\le 2\\cdot 10^5$）个整数 $a_1,a_2,\\ldots,a_N$（$1\\le a_i\\le 10^{11}$），她将会按排序顺序将这些数放入一个单独的数组中。她反复查找这堆数中的最小数，将其删除，同时将其添加到数组的末尾。Bessie 在 $p$ 个数的堆中找到最小数需要花费 $p","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10139"},"statements":[{"statement_type":"Markdown","content":"Bessie 正在尝试使用她自己的排序算法对一个整数数组进行排序。她有一堆共 $N$（$1\\le N\\le 2\\cdot 10^5$）个整数 $a_1,a_2,\\ldots,a_N$（$1\\le a_i\\le 10^{11}$），她将会按排序顺序将这些数放入一个单独的数组中。她反复查找这堆数中的最小数，将其删除，同时将其添加到数组的末尾。Bessie 在 $p$ 个数的堆中找到最小数需要花费 $p$ 秒。\n\nFarmer John 命令了农场中其他一些奶牛帮助 Bessie 完成任务，她们很懒，然而 Bessie 利用了这一点。她将整数分成两堆：Bessie 堆和助手堆。对于 Bessie 堆中的每个整数，她会正常执行她的算法。对于助手堆中的每个整数，她将其分配给不同的助手奶牛。Farmer John 有一个很大的农场，所以 Bessie 可以找来任意多的助手奶牛。如果助手收到整数 $a_i$，Bessie 会指示该牛小睡 $a_i$ 秒，并在她们醒来时立即将该整数添加到数组末尾。如果 Bessie 和一个助手同时向数组添加整数，Bessie 的整数将优先被添加，因为她是领导者。如果多个助手被分配了相同的整数，她们会同时将多个该整数添加到数组中。\n\n请帮助 Bessie 划分她的数，使得最终得到的数组是排序的，并使得排序该数组所需的时间最少。 \n\n## Input\n\n输入的第一行包含 $T$，为独立的测试用例的数量（$1\\le T\\le 10$）。\n\n每个测试用例的格式如下：\n\n每个测试用例的第一行包含 Bessie 的数组中的数的数量 $N$。\n\n下一行包含 $a_1,a_2,\\ldots,a_N$，为 Bessie 将要排序的整数。相同的数值可能会多次出现。\n\n输入保证所有测试用例的 $N$ 之和不超过 $2\\cdot 10^5$。\n\n## Output\n\n 对于每个测试用例输出一行，包含当 Bessie 以最优方案划分她的数时，排序该数组所需要的最小时间。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n在第一个测试用例中，Bessie 可以将 $1,2$ 分配给助手，将 $4,5,10^{11}$ 留给自己。\n\n| 时间 | 事件 |\n| :-----------:| :----------- |\n| $1$ | 助手添加了 $1$ |\n| $2$ | 助手添加了 $2$ |\n| $3$ | Bessie 添加了 $4$ |\n| $5$ | Bessie 添加了 $5$ |\n| $6$ | Bessie 添加了 $10^{11}$ |\n\n在第二个测试用例中，Bessie 的最优方案是自己对所有数进行排序。一个不正确的划分是 Bessie 将 $4$ 分配给助手，其余的分配给她自己，因为助手将 $4$ 添加到数组之前 Bessie 就会将 $17$ 添加到数组中。\n\n在第三个测试用例中，Bessie 可以将所有数都分配给助手。\n\n在第四个测试用例中，Bessie 可以将 $1,4,5$ 分配给助手，将 $2,5,100$ 留给自己。\n\n| 时间 | 事件 |\n| :-----------:| :----------- |\n| $1$ | 助手添加了 $1$ |\n| $3$ | Bessie 添加了 $2$ |\n| $4$ | 助手添加了 $4$ |\n| $5$ | Bessie 添加了 $5$ |\n| $5$ | 助手添加了 $5$ |\n| $6$ | Bessie 添加了 $100$ |\n\n### 测试点性质\n\n- 测试点 $2$：$N\\le 16$。\n- 测试点 $3-5$：$N\\le 150$。\n- 测试点 $6-8$：$\\sum N\\le 5000$。\n- 测试点 $9-11$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10139","tags":["二分","USACO","2024"],"sample_group":[["4\n5\n1 2 4 5 100000000000\n5\n17 53 4 33 44\n4\n3 5 5 5\n6\n2 5 100 1 4 5","6\n15\n5\n6"]],"created_at":"2026-03-03 11:09:25"}}