P10139 [USACO24JAN] Nap Sort G题目描述Bessie 正在尝试使用她自己的排序算法对一个整数数组进行排序。她有一堆共NNN1≤N≤2⋅1051\le N\le 2\cdot 10^51≤N≤2⋅105个整数a1,a2,…,aNa_1,a_2,\ldots,a_Na1​,a2​,…,aN​1≤ai≤10111\le a_i\le 10^{11}1≤ai​≤1011她将会按排序顺序将这些数放入一个单独的数组中。她反复查找这堆数中的最小数将其删除同时将其添加到数组的末尾。Bessie 在ppp个数的堆中找到最小数需要花费ppp秒。Farmer John 命令了农场中其他一些奶牛帮助 Bessie 完成任务她们很懒然而 Bessie 利用了这一点。她将整数分成两堆Bessie 堆和助手堆。对于 Bessie 堆中的每个整数她会正常执行她的算法。对于助手堆中的每个整数她将其分配给不同的助手奶牛。Farmer John 有一个很大的农场所以 Bessie 可以找来任意多的助手奶牛。如果助手收到整数aia_iai​Bessie 会指示该牛小睡aia_iai​秒并在她们醒来时立即将该整数添加到数组末尾。如果 Bessie 和一个助手同时向数组添加整数Bessie 的整数将优先被添加因为她是领导者。如果多个助手被分配了相同的整数她们会同时将多个该整数添加到数组中。请帮助 Bessie 划分她的数使得最终得到的数组是排序的并使得排序该数组所需的时间最少。输入格式输入的第一行包含TTT为独立的测试用例的数量1≤T≤101\le T\le 101≤T≤10。每个测试用例的格式如下每个测试用例的第一行包含 Bessie 的数组中的数的数量NNN。下一行包含a1,a2,…,aNa_1,a_2,\ldots,a_Na1​,a2​,…,aN​为 Bessie 将要排序的整数。相同的数值可能会多次出现。输入保证所有测试用例的NNN之和不超过2⋅1052\cdot 10^52⋅105。输出格式对于每个测试用例输出一行包含当 Bessie 以最优方案划分她的数时排序该数组所需要的最小时间。输入输出样例 #1输入 #14 5 1 2 4 5 100000000000 5 17 53 4 33 44 4 3 5 5 5 6 2 5 100 1 4 5输出 #16 15 5 6说明/提示样例解释 1在第一个测试用例中Bessie 可以将1,21,21,2分配给助手将4,5,10114,5,10^{11}4,5,1011留给自己。时间事件111助手添加了111222助手添加了222333Bessie 添加了444555Bessie 添加了555666Bessie 添加了101110^{11}1011在第二个测试用例中Bessie 的最优方案是自己对所有数进行排序。一个不正确的划分是 Bessie 将444分配给助手其余的分配给她自己因为助手将444添加到数组之前 Bessie 就会将171717添加到数组中。在第三个测试用例中Bessie 可以将所有数都分配给助手。在第四个测试用例中Bessie 可以将1,4,51,4,51,4,5分配给助手将2,5,1002,5,1002,5,100留给自己。时间事件111助手添加了111333Bessie 添加了222444助手添加了444555Bessie 添加了555555助手添加了555666Bessie 添加了100100100测试点性质测试点222N≤16N\le 16N≤16。测试点3−53-53−5N≤150N\le 150N≤150。测试点6−86-86−8∑N≤5000\sum N\le 5000∑N≤5000。测试点9−119-119−11没有额外限制。在这里插入代码片#includebits/stdc.htypedef long long ll;using namespace std;const int N2e55;typedef long long ll;int t,n,c;ll a[N],m,p;int main() {int i,j;scanf(“%d”,t);while(t) {–t;scanf(“%d”,n);for(i1; in; i)scanf(“%lld”,ai);sort(a1,an1);ma[n];for(j1; 1ll*(j1)j/2a[n]; j) {//枚举集合大小pcj;p0;for(i1; in; i) {if(!c)break;if(a[i]pc) {//依次往集合里面塞数ppc;//记录当前Bessie加数的时间–c;}if(in)mmin(m,1llj*(j1)/2);//找答案}if(ma[n])break;}printf(“%lld\n”,m);}return 0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容