暴力贪心: 合并最小权值的果子消耗体力最小, 排序 – 合并 – 找到位置并插入
其中插入合并后的果子应该在那个位置,不可以使用二分,因为我们其实是要将合并之后的序列再全排序,
最坏时间复杂度$O(n^2)$, 最优$O(nlogn)$ 但是因为要预处理(排序),常数大
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int n , ans = 0;
cin>>n;
int a[n+5];
for(int i = 1; i <= n; i++) scanf("%d",a+i);
sort(a+1,a+1+n);
for(int i = 1; i < n ; i++){
ans += a[i]+a[i+1];
a[i+1] += a[i];//合并
for(int j = i+1 ; j < n; j++){
//排序 在合并之后的堆里面找最小的合并
if(a[j] > a[j+1]) swap(a[j+1],a[j]);//这里就是为了把刚刚合并的果子找位置
else break;
}
}
cout<<ans<<endl;
return 0;
}
二叉堆:每次取出最小的两个元素合并,并将合并的结果插入堆中
时间复杂度 $ O(nlogn)$
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 10050;
long long res;
int n, a, b;
inline int read(int &x){
x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
int main(){
read(n);
priority_queue < int,vector<int>,greater<int> > heap;
for(register int i = 1; i <= n; i++) {
read(a);
heap.push(a);
}
while(heap.size()> 1){
a = heap.top(); heap.pop();
b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b);
}
printf("%lld", res);
return 0;
}