堆(优先队列)-搬果子

 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 }