@[我是一个蒟蒻](/user/154952) $C++\space STL$食用更佳
by Fangfx @ 2020-05-01 16:34:14
sort
by xiaomic @ 2020-05-01 16:36:14
@[我是一个蒟蒻](/user/154952) 二叉堆,请。还有这个如果合并了就可能不是最小值。
by SIXIANG32 @ 2020-05-01 16:36:33
a[0]和a[1]不确定最小
by xiaomic @ 2020-05-01 16:37:21
@[我是一个蒟蒻](/user/154952) 啊哦康错了不好意思
by SIXIANG32 @ 2020-05-01 16:37:42
@[我是一个蒟蒻](/user/154952) STL的优先队列它不香吗?
by SIXIANG32 @ 2020-05-01 17:06:23
提醒一下,你这样的时间复杂度为O(n^2logn)是无法AC本题的
by Na2PtCl6 @ 2020-05-01 17:07:20
楼上正解!
by SIXIANG32 @ 2020-05-01 17:09:35
可以改为二分插入
```cpp
#include<algorithm>
using namespace std;
short n;
int a[10004],ans;
int main(){
scanf("%d",&n);
a[n]=30000;
for(int i=0;i<n;i++)
scanf("%d",a+i);
sort(a,a+n);
for(int i=1;i<n;i++){
ans+=a[i]+a[i-1];
a[i]+=a[i-1];
int tmp=a[i];
if(a[i]>a[i+1]){
int p=lower_bound(a+i,a+n,a[i])-a;
for(int j=0;j<=p-1;j++)
a[j]=a[j+1];
a[p-1]=tmp;
}
}
printf("%d",ans);
return 0;
}
```
by Na2PtCl6 @ 2020-05-01 17:20:02
这样虽然不如二叉堆快,但足以通过本题
by Na2PtCl6 @ 2020-05-01 17:21:12