首页 > 代码库 > HDU 5884 Sort ——（K叉哈夫曼树）
HDU 5884 Sort ——（K叉哈夫曼树）
这题真心比较奥义，先见这个人的博客：http://blog.csdn.net/libin66/article/details/52565484
补0的方法是使得其满足成为满K叉树，而其博客中所说的“所以当(n-1)%(k-1)!=0的时候，会出现归并不能最大化个数的情况，这样会影响二分的单调性”我作如下的解释：
至于为什么不加0，sum会变大呢？作如下的解释：因为有一次合并不是最大个数的话，与其让它在后面单独合并增加权值还不如在前面补0合并呢，毕竟我们在算k的时候sum越小越好嘛~
原先代码如下（WA）：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <queue> 5 using namespace std; 6 const int N = 100000 + 5; 7 typedef long long ll; 8 9 int n,lim;10 int a[N];11 12 bool can(int k)13 {14 if(k == 1) return false;15 queue<ll> Q1,Q2;16 ll sum = 0;17 for(int i=1;i<=n;i++) Q1.push((ll)a[i]);18 while(Q1.size()+Q2.size() > 1)19 {20 if(Q1.size()+Q2.size() >= k)21 {22 ll temp = 0;23 for(int i=1;i<=k;i++)24 {25 if(Q2.size()==0)26 {27 temp += Q1.front();Q1.pop();28 }29 else if(Q1.size()==0)30 {31 temp += Q2.front();Q2.pop();32 }33 else if(Q1.front()<=Q2.front())34 {35 temp += Q1.front();Q1.pop();36 }37 else38 {39 temp += Q2.front();Q2.pop();40 }41 }42 sum += temp;43 Q2.push(temp);44 }45 else46 {47 ll temp = 0;48 while(!Q1.empty())49 {50 temp += Q1.front();Q1.pop();51 }52 while(!Q2.empty())53 {54 temp += Q2.front();Q2.pop();55 }56 sum += temp;57 }58 }59 return sum <= (ll)lim;60 }61 62 int main()63 {64 int T;scanf("%d",&T);65 while(T--)66 {67 scanf("%d%d",&n,&lim);68 for(int i=1;i<=n;i++) scanf("%d",a+i);69 sort(a+1,a+1+n);70 int L = 2, R = n;71 int ans = 1;72 while(L <= R)73 {74 //printf("!! %d %d\n",L,R);75 int mid = L + R >> 1;76 if(can(mid))77 {78 ans = mid;79 R = mid - 1;80 }81 else L = mid + 1;82 }83 printf("%d\n",ans);84 }85 return 0;86 }87 88 /*89 690 6 12091 10 10 10 10 1092 */
AC代码如下：
1 #include<iostream> 2 //#include<bits/stdc++.h> 3 #include<cstdio> 4 #include<string> 5 #include<cstring> 6 #include<map> 7 #include<queue> 8 #include<set> 9 #include<stack>10 #include<ctime>11 #include<algorithm>12 #include<cmath>13 #include<vector>14 #define showtime fprintf(stderr,"time = %.15f\n",clock() / (double)CLOCKS_PER_SEC)15 #pragma comment(linker, "/STACK:1024000000,1024000000")16 using namespace std;17 typedef long long ll;18 typedef long long LL;19 #define MP make_pair20 #define PII pair<int,int>21 #define PLI pair<long long ,int> 22 #define PFI pair<double,int>23 #define PLL pair<ll,ll>24 #define PB push_back25 #define F first26 #define S second27 #define lson l,mid,rt<<128 #define rson mid+1,r,rt<<1|129 #define debug cout<<"?????"<<endl;30 //freopen("1005.in","r",stdin);31 //freopen("data.out","w",stdout);32 const int INF = 0x7f7f7f7f;33 const double eps = 1e-2;34 const int M = 1000000 + 50;35 const int N = 1000 + 50 ;36 const double PI = acos(-1.);37 const double E = 2.71828182845904523536;38 const int MOD = 100000007;39 typedef vector<ll> Vec;40 typedef vector<Vec> Mat;41 int T,n,a[100000 + 50];42 ll m;43 bool ok(int k){44 queue<ll> q,p;45 int t = (n-1) % (k-1); 46 // 每次减少k-1个数。一共要减少 (n-1) 个数。 还剩下几个数要和 0 一组了47 if(t != 0) for(int i = 0 ; i < k - t - 1 ; i ++) q.push(0);48 for(int i = 0 ; i < n ; i ++) q.push(a[i]);49 50 ll ans = 0;51 while(!q.empty() || !p.empty()){52 ll tmp = 0;53 for(int i = 0 ; i < k ; i ++){54 if(!q.empty() && !p.empty()){55 ll u = q.front() , v = p.front();56 if(u < v) tmp += u , q.pop();57 else tmp += v , p.pop();58 }else if(!q.empty()){59 ll u = q.front(); q.pop();60 tmp += u;61 }else if(!p.empty()){62 ll v = p.front() ; p.pop();63 tmp += v;64 }else break;65 }66 ans += tmp;67 if(q.empty() && p.empty()) break;68 p.push(tmp);69 }70 return ans <= m;71 }72 void solve(){73 int l = 2 , r = n;74 while(l < r){75 int m = (l+r)>>1;76 if(ok(m)) r = m;77 else l = m + 1;78 }79 cout << l << endl;80 }81 int main(){82 cin >> T;83 while(T --){84 cin >> n >> m;85 for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);86 sort(a,a+n);87 solve();88 }89 return 0;90 }
HDU 5884 Sort ——（K叉哈夫曼树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。