[TIOJ 1398] 霍夫快編碼

作法：

它跟霍夫曼編碼只差在這次要建的東西是個三元樹，所以可以想到核心精神應該還是 greedy 。考慮一個在最優編碼樹裡深度最深的節點，那麼他一定有兄弟，否則把他老爸換成他會更好。如果他有兩個兄弟，那麼這三個數一定是選目前最大的三個數是最好的，證明就根原來的一樣。至於只有一個兄弟的情形，可以先證明，這棵最優編碼樹上頂多只有一個點只有兩的子節點。因為如果有兩個的話，叫他們A和B好了，且A的深度>=B的，那麼可以把A的其中一個子節點移到B下面，另一個子節點移到A，這樣會更好。並且如果最優編碼樹上有個點只有兩個子節點的話，那他那兩個子節點一定深度最深，否則也可以把其他點換上來。這樣我們就得到了一個貪心策略：如果 n 是奇數，那就一直取最小的三個，把他們融合放回去。如果是偶數，那就先融合最小的兩個再繼續作。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
priority_queue<LL,vector<LL>,greater<LL> > pq ;
 
main()
{
    int n ;
    while(scanf("%d",&n)!=EOF)
    {
        while(!pq.empty()) pq.pop() ;
        while(n--)
        {
            LL x ; scanf("%lld",&x) ;
            pq.push(x) ;
        }
        LL ans=0LL ;
        while(pq.size()>=4)
        {
            if(pq.size()%2==0)
            {
                LL x=pq.top() ; pq.pop() ;
                LL y=pq.top() ; pq.pop() ;
                ans+=x+y ; pq.push(x+y) ;
                continue ;
            }
 
            LL x=pq.top() ; pq.pop() ;
            LL y=pq.top() ; pq.pop() ;
            LL z=pq.top() ; pq.pop() ;
            ans+=x+y+z ; pq.push(x+y+z) ;
        }
        while(!pq.empty()) ans+=pq.top() , pq.pop() ;
        printf("%lld\n",ans) ;
    }
}