当前位置：首页 > news >正文

打卡信奥刷题（3414）用C++实现信奥题 P10139 [USACO24JAN] Nap Sort G

news 2026/6/30 23:05:58

P10139 [USACO24JAN] Nap Sort G

题目描述

Bessie 正在尝试使用她自己的排序算法对一个整数数组进行排序。她有一堆共NNN（1≤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

输入 #1

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

输出 #1

6 15 5 6

说明/提示

样例解释 1

在第一个测试用例中，Bessie 可以将1,21,21,2分配给助手，将4,5,10114,5,10^{11}4,5,1011留给自己。

时间	事件
111	助手添加了111
222	助手添加了222
333	Bessie 添加了444
555	Bessie 添加了555
666	Bessie 添加了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	助手添加了111
333	Bessie 添加了222
444	助手添加了444
555	Bessie 添加了555
555	助手添加了555
666	Bessie 添加了100100100

测试点性质

测试点222：N≤16N\le 16N≤16。
测试点3−53-53−5：N≤150N\le 150N≤150。
测试点6−86-86−8：∑N≤5000\sum N\le 5000∑N≤5000。
测试点9−119-119−11：没有额外限制。
`在这里插入代码片
`#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+5;
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(i=1; i<=n; ++i)
scanf(“%lld”,a+i);
sort(a+1,a+n+1);
m=a[n];
for(j=1; 1ll*(j+1)j/2<=a[n]; ++j) {//枚举集合大小p
c=j;
p=0;
for(i=1; i<=n; ++i) {
if(!c)
break;
if(a[i]>=p+c) {//依次往集合里面塞数
p=p+c;//记录当前Bessie加数的时间
–c;
}
if(i==n)
m=min(m,1llj*(j+1)/2);//找答案
}
if(m<a[n])
break;
}
printf(“%lld\n”,m);
}
return 0;
}