首页 > 代码库 > hdu5884 Sort（二分+k叉哈夫曼树）
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的叶子节点作虚拟点。
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 const int N = 100001; 7 int n, m; 8 int a[N]; 9 int jud(int k){10 int i;11 int tt = (n-1)%(k-1);12 ll t, s = 0;13 queue<ll>q1, q2;14 if(tt){15 for(i = 1; i <= k-1 - tt; ++i)16 q1.push(0);//虚拟点17 }18 for(i = 1; i <= n; ++i)19 q1.push(a[i]);20 while(1){21 t = 0;22 int x1, x2;23 for(i = 1; i <= k; ++i){24 if(q1.empty() && q2.empty())25 break;26 if(q1.empty()){27 t += q2.front(); q2.pop();28 continue;29 }30 if(q2.empty()){31 t += q1.front(); q1.pop();32 continue;33 }34 x1 = q1.front();35 x2 = q2.front();36 if(x1 < x2){37 t += x1; q1.pop();38 }else{39 t += x2; q2.pop();40 }41 }42 s += t;43 if(q1.empty() && q2.empty())44 break;45 q2.push(t);//维护合并后的值46 }47 if(s <= m) return 1;48 return 0;49 }50 void bi_search(){51 int l = 2,r = n;52 while(l < r){53 int mid = l + (r - l)/2;54 if(jud(mid))55 r = mid;56 else57 l = mid + 1;58 }59 printf("%d\n", r);60 }61 int main(){62 int t, i;63 scanf("%d", &t);64 while(t--){65 scanf("%d%d", &n, &m);66 for(i = 1; i <= n; ++i)67 scanf("%d", &a[i]);68 sort(a+1, a+1+n);69 bi_search();70 }71 return 0;72 }
hdu5884 Sort（二分+k叉哈夫曼树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。