一座高度为k的塔\(b1,b_2,\dots,b_k\)满足\(2b_1\leq b_2,2b_2\leq b_3,2b_3\leq b_4,\dots,2b{k-1}\leq b_k\)
你要从中选择一些数来叠很多座高度为\(k\)的塔，问最多能叠多少座塔。
Input
第一行包含一个正整数T(1≤T≤10)，表示测试数据的组数。
每组数据第一行包含两个正整数n,k(2≤n≤100000,2≤k≤30)。
第二行包含\(n\)个正整数\(a_1,a_2,\dots,a_n(1\leq a_i\leq 10^9)\)。
Output
对于每组数据输出一行一个整数，即能叠出的塔的数量。
输入样例
3
4 2
1 2 3 4
6 3
1 1 2 2 4 4
6 3
1 1 2 2 3 4
输出样例
2
2
1
数学--构造二分
因为若能够搭出x座塔，必然可以搭出x-1座塔，直接二分查找最大的x即可，关键在判断能否搭成x座k层高的塔，贪心枚举即可
注意无解的特判，让二分范围在[1,n]
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,k;
int a[N];
bool f(int x)//返回能否叠出x座k层塔
{
//利用贪心分析:如能够搭出x座塔,用最小的x个ai座塔底一定是一个解
vector<int> v[x+1];
int cnt=0;
for(int i=1;i<=n;++i)
{
cnt%=x;
if(v[cnt].empty()||a[i]>=2*v[cnt].back())
{
v[cnt].push_back(a[i]);
cnt++;
}
//cout<<v[0].size()<<' '<<v[1].size()<<'\n';
}
for(int i=0;i<x;++i) if(v[i].size()<k) return false;
return true;
}
int bina(int mi,int ma)//二分的目的:找到最大的x使得f(x)=true
{
int l=mi,r=ma,ans=r;
while(l<=r)
{
int mid=(l+r)>>1;
bool tmp=f(mid);
if(tmp) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;++i) cin>>a[i];
sort(a+1,a+1+n);
if(!f(1)) cout<<'0'<<'\n';//特判一下无解的情况因为x不能做被模数
else
cout<<bina(1,n/k)<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}