1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 const int N=300010; 7 int a[N],n,S,f1,f2,b1,b2; 8 int q1[N],q2[N]; 9 bool Check(int k){10     f1=b1=f2=b2=0;11     for(int i=1;i<=n;i++)12         q1[b1++]=a[i];13     for(int i=0;(n+i-1)%(k-1);i++)14         q2[b2++]=0;15     int tot=0,tmp;16     while(true){tmp=0;17         for(int i=1;i<=k;i++){18             if(f1==b1)tmp+=q2[f2++];19             else if(f2==b2)tmp+=q1[f1++];20             else if(q1[f1]<q2[f2])tmp+=q1[f1++];21             else tmp+=q2[f2++];22         }tot+=tmp;23         if(f1>=b1&&f2>=b2)break;24         q2[b2++]=tmp;25     }    26     return tot<=S;27 }28 int main(){29     int T;30     scanf("%d",&T);31     while(T--){32         scanf("%d%d",&n,&S);33         for(int i=1;i<=n;i++){34             scanf("%d",&a[i]);35         }     36         sort(a+1,a+n+1);37         int lo=2,hi=n;38         while(lo<=hi){39             int mid=(lo+hi)>>1;40             if(Check(mid))hi=mid-1;41             else lo=mid+1;42         }43         printf("%d\n",lo);44     }45     return 0;46 }