Sort HDU5884（二分+多叉哈夫曼树）

HDU5884 Sort

题意：有n个序列要进行归并，每次归并的代价是两个序列的长度的和，要求最终的代价不能超过规定的T，求在此前提下一次能同时进行归并的序列的个数k。

思路：还是太单纯，看完题目一直以为要用归并排序来解题，如果已经看过多叉哈夫曼树的知识的话估计就不会这样了。先二分查找这个k，然后用多叉哈夫曼树来判断这个k是不是还能再变小。用两个队列来实现多叉哈夫曼树。

PS：如果不进行提前处理的话，最后一次的归并可能就凑不齐k个来了，所以需要提前处理一下。

代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <set>

#include <queue>

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

//typedef pair<int,int> P;

queue<ll> q1;

queue<ll> q2;

int T,n;

ll a[maxn];

ll t;

bool Hufman(int x)

{

    while (!q1.empty()) q1.pop();

    while (!q2.empty()) q2.pop();

    int tt = (n - ) % (x - );

    if (tt)

    {

        for (int i = ; i <= x -  - tt; i++)//添加虚构0，使得最后一次能凑齐k个序列，手动模拟了一下求tt的过程，

            q1.push();//但不明白n-1具体的原因，不知是不是固定的模式

    }

    for (int i = ; i <= n; i++)

        q1.push(a[i]);

    ll sum = ;

    while ()

    {

        ll tem = ;

        for (int i = ; i <= x; i++)

        {

            if (q1.empty() && q2.empty())break;

            if (q1.empty())

            {

                tem += q2.front();

                q2.pop();

            }

            else if (q2.empty())

            {

                tem += q1.front();

                q1.pop();

            }

            else

            {

                int tx, ty;

                tx = q1.front();

                ty = q2.front();

                if (tx < ty)

                {

                    tem += tx;

                    q1.pop();

                }

                else

                {

                    tem += ty;

                    q2.pop();

                }

            }

        }

        sum += tem;

        if (q1.empty() && q2.empty())break;

        q2.push(tem);//q2这个序列一定是有序的

    }

    if (sum <= t)

        return ;

    else

        return ;

}

int main()

{

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d%lld", &n, &t);

        for (int i = ; i <= n; i++)

            scanf("%lld", &a[i]);

        sort(a + , a +  + n);

        int st = , en = n;

        while (st < en)

        {

            int mid = (st + en) / ;

            if (Hufman(mid))

                en = mid;

            else

                st = mid + ;

            //printf("GG\n");

        }

        printf("%d\n", st);

    }

    return ;

}