@[Diary_51](/user/925688) 大根堆
by Humour_Fz @ 2024-02-21 14:55:28
你为啥要在for循环里排序？
by zhangbomingpp @ 2024-02-21 14:55:53
@[Diary_51](/user/925688) $O(n^2logn)$ 必超时啊
by OSCAR313 @ 2024-02-21 14:57:10
@[Diary_51](/user/925688) 可以使用[优先队列](https://blog.csdn.net/xingzi201/article/details/119884227)
by OSCAR313 @ 2024-02-21 15:00:51
@[Diary_51](/user/925688) 把快排换成插入排序就行了```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[10010];
ll sum;
bool cmp(int x, int y) {
return x > y;
}
void pai(int a[], int x) {
int s = a[x];
int j = x - 1;
while (j >= 1 && a[j] < s) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = s;
return;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a + 1, a + 1 + n, cmp);
int r = n;
while (r >= 2) {
a[r - 1] = a[r] + a[r - 1];
sum += a[r - 1];
r--;
pai(a, r);
}
cout << sum << endl;
return 0;
}
```
by AHuLei @ 2024-03-08 19:04:33
@[Diary_51](/user/925688) 用归并也可以擦边过
by AHuLei @ 2024-03-08 19:06:58
改一下，用vector也可以过
```cpp
#include <bits/stdc++.h>
using namespace std;
vector <int> vt;
int main() {
int n, s = 0;
cin >> n;
for (int i = 1, x; i <= n; i++)
cin >> x, vt.insert(upper_bound(vt.begin(), vt.end(), x), x);
while (vt.size() != 1) {
int sum = vt[0] + vt[1];
vt.erase(vt.begin());
vt.erase(vt.begin());
vt.insert(upper_bound(vt.begin(), vt.end(), sum), sum);
s += sum;
}
cout << s << endl;
return 0;
}
```
就是二分插入排序，还挺好理解的
by Chase12345 @ 2024-04-02 23:54:30