[Leaf] [P6033] 合并果子

luogu-p6033-合并果子">Luogu-P6033 合并果子

1. 核心逻辑

• 问题本质: 求哈夫曼树的最小带权路径长度。在 $N=10^7$ 下规避 $O(N \log N)$ 的优先队列。

• 破局转换:

  1. 单调性: 在输入有序的前提下，新合成出的节点权值也具备单调递增性。

  2. 双队列优化:

     • q1: 存放初始权值（桶排序后推入，天然有序）。

     • q2: 存放新合成的权值（按合成顺序推入，天然有序）。

     • 每次从两队首取最小值，实现 $O(N)$ 贪心实现。

2. 代码实现

▶

AcCode

// P6033 合并果子 (Greedy Huffman)
// Key Logic: O(N) Huffman tree building with dual monotonic queues

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int maxv = 1e5 + 50;
const int maxn = 1e7 + 50;

int cnt[ maxv ];
int q1[ maxn ], h1 = 1, t1 = 0;
ll q2[ maxn ], h2 = 1, t2 = 0;

ll get( )
{
    if( h1 > t1 ) return q2[ h2 ++ ];
    if( h2 > t2 ) return q1[ h1 ++ ];
    return q1[ h1 ] < q2[ h2 ] ? q1[ h1 ++ ] : q2[ h2 ++ ];
}

int main( )
{
    int n;
    scanf( "%d", &n );
    for( int i = 1; i <= n; ++ i )
    {
        int x;
        scanf( "%d", &x );
        cnt[ x ] ++;
    }

    for( int i = 1; i < maxv; ++ i )
    {
        while( cnt[i] -- ) q1[ ++ t1 ] = i;
    }

    ll ans = 0;
    for( int i = 1; i < n; ++ i )
    {
        ll x = get( );
        ll y = get( );
        ans += x + y;
        q2[ ++ t2 ] = x + y;
    }

    printf( "%lld\n", ans );
    return 0;
}

3. 归档备注

• 策略: 桶排序在值域较小时可替代 $O(N \log N)$ 排序。

• 相关知识点：贪心策略