这题真心比较奥义，先见这个人的博客：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 else 38 { 39 temp += Q2.front();Q2.pop(); 40 } 41 } 42 sum += temp; 43 Q2.push(temp); 44 } 45 else 46 { 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 ",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 ",ans); 84 } 85 return 0; 86 } 87 88 /* 89 6 90 6 120 91 10 10 10 10 10 92 */
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 ",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_pair 20 #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_back 25 #define F first 26 #define S second 27 #define lson l,mid,rt<<1 28 #define rson mid+1,r,rt<<1|1 29 #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 }