思路:用朴素的方法实现的话,时间复杂度为O(n^n)。因为只需要从板的集合中取出最短的两块,并且把长度为两块长度之和的板加入集合中即可,所有使用优先队列就可以高效的实现。一共需要进行O(n)次O(log N)的操作,因此总的时间复杂度为O(Nlogn)。
#include<bits/stdc++.h>
#define maxn 100003
using namespace std;
int l[maxn];
bool solve(){
ll ans = 0;
priority_queue<int,vector<int>,greater<int> > que;
for(int i=0;i<n;i++){
que.push(l[i]);
}
while(que.size()>1){
int l1,l2;
l1 = que.top();
que.pop();
l2 = que.top();
que.pop();
ans += l1+l2;
que.push(l1+l2);
}
cout<<ans<<endl;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>l[i];
solve();
return 0;
}