poj 3253 Fence Repair

贪心，这是挑战程序设计竞赛书上的一种方法，略微奇特的贪心。用到了二叉树的思想，还是很有意思的。

 1 //
 2 //  main.cpp
 3 //  poj 3253
 4 //
 5 //  Created by dada on 2017/2/15.
 6 //  Copyright © 2017年 dada. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include<algorithm>
11 #define MAX_N 20005
12 typedef long long ll;
13 
14 using namespace std;
15 
16 int n,l[MAX_N];
17 
18 void solve()
19 {
20     ll ans=0;
21     while(n>1)
22     {
23         int mii1 = 0, mii2 = 1;
24         if(l[mii1] > l[mii2])
25             swap(mii1,mii2);
26         
27         for(int i = 2; i < n; i++)
28         {
29             if(l[i] < l[mii1])
30             {
31                 mii2 = mii1;
32                 mii1=i;
33             }
34             else if(l[i] < l[mii2])
35             {
36                 mii2=i;
37             }
38         }
39     
40     
41         int t = l[mii1]+l[mii2];
42         ans+=t;
43     
44         if(mii1 == n-1)
45             swap(mii1,mii2);
46         l[mii1] = t;
47         l[mii2] = l[n-1];
48         n--;
49     }
50     cout<<ans<<endl;
51 }
52 int main()
53 {
54     while(cin>>n)
55     {
56         for(int i = 0; i < n; i++)
57             cin>>l[i];
58         solve();
59     }
60     return 0;
61 }