82 lines
1.6 KiB
C++
82 lines
1.6 KiB
C++
#include <iostream>
|
||
#include <algorithm>
|
||
#include <stdio.h>
|
||
#include <queue>
|
||
#include <cmath>
|
||
#include <string.h>
|
||
using namespace std;
|
||
int N;
|
||
long long T;
|
||
long long a[100005];
|
||
|
||
int calc(int k)
|
||
{
|
||
queue<long long>q;
|
||
int pos=0;
|
||
long long sum=0;
|
||
if((N-1)%(k-1)!=0&&N>k) ///如果不能k个k个合并到底，则先合并筹不足k个的；
|
||
{
|
||
pos=(N-1)%(k-1)+1;
|
||
for(int i=0;i<pos;i++) sum+=a[i];
|
||
q.push(sum);
|
||
}
|
||
while(1)
|
||
{
|
||
long long sum2=0;
|
||
for(int i=0; i<k; i++)
|
||
{
|
||
if(!q.empty())
|
||
{
|
||
if(pos<N&&q.front()>a[pos])
|
||
{
|
||
sum2+=a[pos];
|
||
sum+=a[pos];
|
||
pos++;
|
||
}
|
||
else
|
||
{
|
||
sum2+=q.front();
|
||
sum+=q.front();
|
||
q.pop();
|
||
}
|
||
}
|
||
else if(pos<N)
|
||
{
|
||
sum2+=a[pos];
|
||
sum+=a[pos];
|
||
pos++;
|
||
}
|
||
else goto endw;
|
||
}
|
||
if(sum>T) return 0;
|
||
if(pos<N||!q.empty())
|
||
q.push(sum2);
|
||
}
|
||
endw:;
|
||
if(sum<=T) return 1;
|
||
else return 0;
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int to;
|
||
scanf("%d",&to);
|
||
while(to--)
|
||
{
|
||
scanf("%d%lld",&N,&T);
|
||
for(int i=0; i<N; i++)
|
||
scanf("%lld",&a[i]);
|
||
sort(a,a+N);
|
||
int l=2,r=N,mid;
|
||
while(l<=r)
|
||
{
|
||
mid=(l+r)>>1;
|
||
int f=calc(mid);
|
||
if(f==0) l=mid+1;
|
||
else r=mid-1;
|
||
}
|
||
printf("%d\n",l);
|
||
}
|
||
return 0;
|
||
}
|