题意：

给出n个数字，要求合并这些数字的代价不超过T，每次可以合并不超过k个数字，每次合并的代价为这些数字的和。问最小的k可以是多少。其中$2≤N≤100000$。

思路：

容易想到二分这个k。

但是这里合并的时候有个问题，不能直接取当前最小的几个合并，因为可能会出现最后一次合并剩下的不是k的情况，这样子就不能最优了。比如这个例子1 2 3 4 5 6，k=3的时候，如果直接取的话代价为6+15+21，事实上要先取两个最小的，代价为3+10+21，所以有个结论：

对于k叉树，设m为叶子数 , 若$( m - 1 ) \% ( k - 1 ) != 0$, 要增加虚(子叶)结点。第一次构造用$( m - 1 ) \% ( k - 1 ) + 1$个结点，之后都用k个结点构造k叉树。

这里又有个问题，如果直接用优先队列，总的复杂度为$O(n*logn*logn)$，还有t组，网上说可以卡过去，然而我并没有卡过去。

所以这里可以用单调队列，把产生的新的和放入队列，数列从小到大排列，每次取最小的数字的时候，把队首元素和数组里的数字进行比较可以了。这样保证队列中队首元素总是最小的。

代码：

typedef long long ll;
ll a[100010];
int n;
ll MAX;
bool judge(int x)
{
    //printf("x=%d\n",x);
    queue<ll>q;
    int pos=1;
    ll tot=0;
    if((n-1)%(x-1)!=0)
    {
        int temp=(n-1)%(x-1)+1;
        ll sum=0;
        for(int i=0; i<temp; i++)
        {
            sum+=a[pos];
            pos++;
        }
        q.push(sum);
        tot+=sum;
    }
    //printf("tot=%lld pos=%d\n",tot,pos);
    while(1)
    {
        ll sum=0;
        for(int i=0; i<x; i++)
        {
            if(pos==n+1||(!q.empty()&&q.front()<a[pos]))
            {
                sum+=q.front();
                //printf("%lld ",q.front());
                q.pop();
            }
            else
            {
                sum+=a[pos];
                //printf("%lld ",a[pos]);
                pos++;
            }
        }
        //printf("\n");
        q.push(sum);
        //printf("%d %lld\n",pos,sum);
        tot+=sum;
        if(pos==n+1&&q.size()==1)break;
    }
    //printf("%lld\n",tot);
    if(tot<=MAX)return true;
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lld",&n,&MAX);
        for(int i=1; i<=n; i++)
            scanf("%lld",&a[i]);
        if(n==1){printf("0\n");continue;}
        sort(a+1,a+1+n);
        int l=2,r=n,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(judge(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}