D. Ice Cream Tower
C语言题库
共 934字，需浏览 2分钟
·
2021-04-22 20:25
解法：如果能做x个冰淇淋塔的话，那么最优做法必然是先取最小的x个冰淇淋球作为第一层，然后一层一层往下铺。可以把冰淇淋球从小到大排序，然后二分枚举x的值，依次判断能否做成即可。复杂度O(NlogN)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int n,k;
ll a[N],b[N];
bool ok(int x)
{
for(int i=0; i<x; ++i)
b[i]=a[i];
int t=0,cnt=1;
for(int i=x; i<n; ++i)
{
if(a[i]/b[t]>=2)
{
if(t==x-1)
++cnt;
b[t]=a[i];
t=(t+1)%x;
}
}
return cnt>=k;
}
int main()
{
int T,kase=0;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=0; i<n; ++i)
scanf("%lld",&a[i]);
sort(a,a+n);
int l=0,r=n;
while(l<r)
{
int mid=(l+r+1)>>1;
ok(mid)?l=mid:r=mid-1;
}
printf("Case #%d: %d\n",++kase,l);
}
return 0;
}
评论