果园里面有n堆果子,每堆果子有xi个,每个果子的重量为1,小明每次把i,j两堆果子移成一堆,需要花费的体力为xi+xj。最后移成一堆,求最小花费体力值。
其中1<=n<=10000,1<=m<=10000。均为正整数。Input

    每组数据第一行输入一个正整数n,表示有n堆果子。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

    接下来一行有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 }

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄