题意:现在在1盒子中有N中颜色的求各ai个,要求操作若干次使得颜色i的球全部进入i盒子中,操作为:从某个盒子中取出所有的球,花费是取出球的总个数,然后把这些球分成k堆,放到k个空的盒子中去,k=2或者3.求最小花费。
题解:反过来想,就是合并果子嘛。求一个带权路径和最小值,就是3-哈夫曼树。显然3-哈夫曼树比2-哈夫曼树更优,但是2-哈夫曼树对于任意个数的果子都可以构造出来,因为每次2->1,每次减少一个果子。但是3-哈夫曼树,每次3->1,每次减少两个,这就要求果子总数为奇数,如果给定的果子总数是偶数,那么就加一个0果子进去就完事了。
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long LL;
priority_queue<LL,vector<LL>,greater<LL> >pq;
int n;
LL sum =0;
int main(){
scanf("%d",&n);
for (int i=0;i<n;i++){
int val;
scanf ("%d",&val);
pq.push(val);
}
if (n&1);else pq.push(0);
while (pq.size()>1){
LL temp = pq.top();pq.pop();
temp+=pq.top();pq.pop();
temp+=pq.top();pq.pop();
sum+=temp;
pq.push(temp);
}
cout<<sum<<endl;
return 0;
}