堆(优先队列)-搬果子
果园里面有n堆果子，每堆果子有xi个，每个果子的重量为1，小明每次把i,j两堆果子移成一堆，需要花费的体力为xi+xj。最后移成一堆，求最小花费体力值。
其中1<=n<=10000,1<=m<=10000。均为正整数。Input
每组数据第一行输入一个正整数n，表示有n堆果子。
接下来一行有n个正整数，表示每堆果子的重量。
输入以EOF结尾。
Output 每组数据单独一行，输出所花费的最小体力值。
Sample Input
3
1 2 9
5
1 3 9 18 30
Sample Output
15
109
首先可以贪心地每次将最小和第二小的果堆合起来,可是合成后的堆不一定比原来第三小的堆小,如33456合成后就变成6456,显然6+4>4+5,因此我们需要动态排序,由此想到了优先队列.
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int amn=1e5+5; 5 int a[amn]; 6 int n; 7 void sd(int i) 8 { 9 int t; 10 while(2*i<=n) 11 { 12 if(a[i]>a[2*i])t=2*i;///先判断左孩子 13 else t=i; 14 if(2*i+1<=n&&a[t]>a[2*i+1])t=2*i+1;///如果右孩子存在,则判断右孩子 15 if(t!=i) 16 { 17 swap(a[i],a[t]); 18 i=t;///注意要更新编号,下一次循环才会继续调整; 19 } 20 else break; 21 } 22 } 23 void up(int i) 24 { 25 int t; 26 while(i<=1) 27 { 28 if(i/2<=1&&a[i]<a[i/2])t=i/2; 29 else t=i; 30 if(t!=i) 31 { 32 swap(a[i],a[t]); 33 i=t; 34 } 35 else break; 36 } 37 } 38 void create() 39 { 40 for(int i=n/2;i>=0;i--) 41 sd(i); 42 } 43 int del() 44 { 45 int t=a[1]; 46 a[1]=a[n]; 47 n--; 48 sd(1); 49 return t; 50 } 51 void push(int i) 52 { 53 a[++n]=i; 54 sd(n); 55 } 56 int main() 57 { 58 while(cin>>n) 59 { 60 for(int i=1;i<=n;i++) 61 cin>>a[i]; 62 create(); 63 int ans=0; 64 while(1) 65 { 66 int tmp=del(); 67 tmp+=del(); 68 ans+=tmp; 69 if(!n)break;///注意在这里空了就要跳出,否则会合出原来就不存在的堆 70 push(tmp); 71 } 72 cout<<ans<<endl; 73 } 74 }
哔哩哔哩公司氛围 96人发布