@[Dream_perday](/user/1218760)
普通当模板一样打暴力快排会爆的,你这样干最坏时间复杂度为 $n^3$ ,而 $n<=10000$ ,肯定会T ,正确解法可以使用C++的STL库里的数据结构priority_queue优先队列(最容易理解也最容易写,可以看题解也可以网上搜这个数据结构),也可以手写优化的sort函数(极其麻烦),还有各种方法再此不列举了。
by youzhanyue @ 2024-02-03 14:25:42
@[youzhanyue](/user/502121) 好的,感谢。
by Dream_perday @ 2024-02-03 14:33:41
@[Dream_perday](/user/1218760)
循环感觉有点问题
可以改成这样
```
for(t=0;t<n-1;t++){
sort(a+t,a+n);
a[t+1]=a[t]+a[t+1];
sum=sum+a[t+1];
}
by _3247535661_ @ 2024-02-03 14:34:25
@[_3247535661_](/user/1040109)
刚刚用优先队列解决了,可能问题还是在1楼说的那个,sort太多次爆了。
```cpp
#include<iostream>
#include<algorithm>
#include<limits.h>
#include<queue>
using namespace std;
int main()
{
int t,i,n,sum=0,tmp=0,m;
priority_queue<int,vector<int>,greater<int>> a;
cin>>n;
for(i=0;i<n;i++)
{
cin>>m;
a.push(m);
}
for(t=n;t>1;t--)
{
sum+=a.top();
tmp+=a.top();
a.pop();
sum+=a.top();
tmp+=a.top();
a.pop();
a.push(tmp);
tmp=0;
}
cout<<sum;
}
```
改成这样就通过了。
by Dream_perday @ 2024-02-03 15:02:28
@[Dream_perday](/user/1218760) sort是内省排序,情况不对会开堆排,最优、期望与最劣复杂度均为$O(logn)$,不存在退化的问题。
不过对于$n\leq10000O(n^2logn)$也确实太大了$\cdots$
by litjohn @ 2024-02-19 20:31:53