@[wuhusjqif](/user/1193780) 做法假了,HACK:
4
3 4 5 6
by sdyzpf @ 2023-11-27 19:32:21
@[sdyzpf](/user/174477) 您好没看懂
by wuhusjqif @ 2023-11-27 19:36:14
@[wuhusjqif](/user/1193780) 啊
by heyx0201 @ 2023-11-27 19:39:31
@[wuhusjqif](/user/1193780) 这题 C 语言很难做,
by heyx0201 @ 2023-11-27 19:39:52
@[wuhusjqif](/user/1193780) 除非你手写堆
by heyx0201 @ 2023-11-27 19:40:01
@[wuhusjqif](/user/1193780) 给一份 C++ 代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
priority_queue<int,vector<int>,greater<int>>q;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> x, q.push(x);
while (q.size() >= 2) {
int a = q.top(); q.pop();
int b = q.top(); q.pop();
ans += a + b;
q.push(a + b);
}
cout << ans << endl;
return 0;
}
```
by heyx0201 @ 2023-11-27 19:41:12
@[wuhusjqif](/user/1193780) 就是这种排序后相加的做法是错误的。比如这个数据:
4
3 4 5 6
按照你的做法,会先3+4,再7+5,再12+6。
然而实际上最优的做法是先3+4,再5+6,再7+11
by sdyzpf @ 2023-11-27 21:06:34
@[sdyzpf](/user/174477) 感谢
by wuhusjqif @ 2023-11-27 21:38:36
@[heyx0201](/user/768951) 不会c++但是感谢了
by wuhusjqif @ 2023-11-27 21:39:00