hdu5884 Sort（二分+k叉哈夫曼树）

题目链接：hdu5884 Sort

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

题解：先二分k，然后在k给定的情况下，构造k叉哈夫曼树。O(nlogn)的做法：先对所有数排序，另外一个队列维护合并后的值，取值时从两个序列前端取小的即可。

注：如果（n-1）%（k-1）！=0，那么就要增加（k-1-（n-1）%（k-1））个权值为0的叶子节点作虚拟点。

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int N = ;

 int n, m;

 int a[N];

 queue<ll>q1, q2;

 int jud(int k){

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

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

     //queue<ll>q1, q2;

     int i;

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

     ll t, s = ;

     if(tt){

         for(i = ; i <= k- - tt; ++i)

             q1.push();//虚拟点

     }

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

         q1.push(a[i]);

     while(){

         t = ;

         int x1, x2;

         for(i = ; i <= k; ++i){

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

                 break;

             if(q1.empty()){

                 t += q2.front(); q2.pop();

                 continue;

             }

             if(q2.empty()){

                 t += q1.front(); q1.pop();

                 continue;

             }

             x1 = q1.front();

             x2 = q2.front();

             if(x1 < x2){

                 t += x1; q1.pop();

             }else{

                 t += x2; q2.pop();

             }

         }

         s += t;

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

             break;

         q2.push(t);//维护合并后的值

     }

     if(s <= m) return ;

     return ;

 }

 void bi_search(){

     int l = ,r = n;

     while(l < r){

         int mid = l + (r - l)/;

         if(jud(mid))

             r = mid;

         else

             l = mid + ;

     }

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

 }

 int main(){

     int t, i;

     scanf("%d", &t);

     while(t--){

         scanf("%d%d", &n, &m);

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

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

         sort(a+, a++n);

         bi_search();

     }

     return ;

 }