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 }