題目

有n堆大小不同的果子堆，每次合并兩堆消耗它們兩堆的重量之和，求把它們全部合并的最小消耗

---

輸入

輸入包括兩行，第一行是一個整數n(1<＝n<=10000)，表示果子的種類數。第二行包含n個整數，用空格分隔，第i個整數ai(1<＝ai<=20000)是第i種果子的數目。

輸出

輸出包括一行，這一行只包含一個整數，也就是最小的體力耗費值。輸入數據保證這個值小于2^31。

樣例輸入

3
1 2 9

樣例輸出

15

---

解題思路

貪心就是每次都合并最小的兩個，這里用堆可以方便一些

---

代碼

#include<cstdio> using namespace std; int a[10001],num,x,n; long long s,u; void up(int x) {int t;while (x>1 && a[x]<a[x/2]){t=a[x];a[x]=a[x/2];a[x/2]=t;x/=2;} }//調整堆 void down(int x) {int t,y;while (x*2<=num && a[x]>a[x*2] || x*2+1<=num && a[x]>a[x*2+1]){y=x*2;if (x*2+1<=num && a[x*2]>a[x*2+1]) y++;t=a[x];a[x]=a[y];a[y]=t;x=y;} }//調整堆 void insert(int x) {a[++num]=x;up(num);}//插入元素 int main() {scanf("%d",&n); for (int i=1;i<=n;i++){scanf("%d",&x);insert(x);}//建堆while (num>1){u=a[1];a[1]=a[num];num--;down(1);u+=a[1];a[1]=a[num];num--;down(1);//取兩個最小的s+=u;num++;a[num]=u;up(num);//合并后放回}printf("%d",s); }

總結

以上是生活随笔為你收集整理的jzoj1082-合并果子【堆,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。