【最优K叉树】hdu 5884 Sort

http://acm.hdu.edu.cn/showproblem.php?pid=5884

参考：https://www.cnblogs.com/jhz033/p/5879452.html

【题意】

n个有序序列的归并排序.每次可以选择不超过k个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T, 问k最小是多少。

【思路】

k越大，代价越小，二分k，check k

对于每个k，问题转化为n个结点的最优k叉树，用堆做时间复杂度为O(nlogn)，再加上二分总复杂度是O(nlogn^2)

然后T了。。。听说加输入挂可以卡过去

正解是这样的：

原数组排序，预处理时间复杂度O(nlogn)

然后求最优k叉树，用一个队列维护合并后的值，而不需要加入原来的堆里重排序（利用新加入的内结点本身的单调性），每次时间复杂度为O(n)

O(nlogn)+O(logn)*O(n)，所以最后时间复杂度是O(nlogn)

n个结点不一定能构成最优k叉树，需要补 k-1-((n-1)%(k-1))个权为0的虚结点。

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 int n;

 ll t;

 const int maxn=1e5+;

 ll a[maxn];

 bool judge(int mid){

     int cnt=(n-)/(mid-);

     queue<ll> Q;

     if((n-)%(mid-)!=){

         cnt++;

         for(int i=;i<(mid--(n-)%(mid-));i++){

             Q.push();

         }

     }

     ll ans=;

     int l=;

     while(cnt--){

         ll tmp=;

         for(int i=;i<mid;i++){

             if(!Q.empty()&&(l>=n||Q.front()<=a[l])){

                 tmp+=Q.front();

                 Q.pop();

             }else{

                 tmp+=a[l++];

             }

         }

         ans+=tmp;

         Q.push(tmp);

     }

     if(ans<=t) return true;

     return false;

 }

 int main(){

     int T;

     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 l=,r=n;

         while(l<=r){

             int mid=(l+r)>>;

             if(judge(mid)){

                 r=mid-;

             }else{

                 l=mid+;

             }

         }

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

     }

     return ;

 }

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

typedef long long ll;

int n;

ll t;

const int maxn=1e5+;

ll a[maxn];

bool judge(int mid){

    queue<ll> Q1,Q2;

    for(int i=;i<n;i++) Q1.push(a[i]);

    if((n-)%(mid-)!=){

        for(int i=;i<(mid--(n-)%(mid-));i++){

            Q2.push();

        }

    }

    ll ans=;

    while(Q1.size()+Q2.size()>=mid){

        ll tmp=;

        for(int i=;i<mid;i++){

            if(Q1.empty()&&!Q2.empty()){

                tmp+=Q2.front();

                Q2.pop();

            }else if(Q2.empty()&&!Q1.empty()){

                tmp+=Q1.front();

                Q1.pop();

            }else if(!Q1.empty()&&!Q2.empty()){

                if(Q1.front()<=Q2.front()){

                    tmp+=Q1.front();

                    Q1.pop();

                }else{

                    tmp+=Q2.front();

                    Q2.pop();

                }

            }

        }

    //    cout<<tmp<<endl;

        ans+=tmp;

        Q2.push(tmp);

    }

    if(ans<=t) return true;

    return false;

}

int main(){

    int T;

    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 l=,r=n;

        while(l<=r){

            int mid=(l+r)>>;

            if(judge(mid)){

                r=mid-;

            }else{

                l=mid+;

            }

        }

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

    }

    return ;

}