bzoj4198 [Noi2015] [荷馬史詩] Huffman 編碼

1.維護k叉樹，注意補零

2.用堆來維護最小的頻率和長度，每次向上合并，在合并時統計答案

3.如果 n % （k-1）=1那麼就不用補零（因為每次合并就相當于增加k-1個節點，所有如果能合并成一個節點，那麼一定符合上面的條件）

# include <queue>
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
# define LL long long

using namespace std;

inline LL Read () {
    LL x =  , f =  ;
    char ch = getchar () ;
    while ( ! isdigit ( ch ) ) {
        if ( ch == '-' ) f = - L ;
        ch = getchar () ;
    }
    while ( isdigit ( ch ) ) {
        x = L * x *  + ch - '0' ;
        ch = getchar () ;
    }
    return x * f ;
}

struct P{
    LL len , p ;
    P ( LL x =  , LL y =  ) : len ( x ) , p ( y ) {}
    bool operator<( const P & rhs ) const {
        if ( p == rhs.p ) return len > rhs.len ;
        return p > rhs.p ;
    }
} an;

priority_queue <P> Q ;

int main () {
//  freopen ( "debug.in" , "r" ,stdin ) ;
    LL n , k ;
    n = Read () , k = Read () ;
    for ( int i =  ; i <= n ; ++ i ) {
        LL x = Read () ;
        Q.push ( P (  , x ) ) ;
    }
    while ( k >  && n % ( k -  ) !=  ) {
        n ++ ;
        Q.push ( P (  ,  ) ) ;
    }
    while (  Q.size () >  ) {
        int p = k ;
        LL ll =  , pp =  ;
        while ( p && ! Q.empty () ) {
            P e = Q.top () ;
            Q.pop () ;
            ll = max ( ll , e.len +  ) , pp += e.p ;
            p -- ;
        }
        an.p += pp , an.len = max ( an.len , ll ) ;
        Q.push ( P ( ll , pp ) ) ;
    }
    P e = Q.top () ;
    printf ( "%lld\n%lld" , an.p , an.len ) ;
    return  ;
}