admin 管理员组

文章数量: 887039

G

题意：

给定n个冰淇淋球，问能组成最多多少个由k个冰淇淋球堆成的冰淇淋，并且满足下面的冰淇淋球的面积是上面冰淇淋球面积的二倍。

 

题解：

正解：

对结果进行二分

二分内容：

判定能否堆成m堆，先用b[]的前m个作为每堆的最上面一个a[m]，
每堆找k-1个，从剩下的冰淇淋中找第一个>=当前j堆a[j]*2，更新堆底，能堆成返回真否则返回假。

 

const int maxn=3e5+1000;int n,k;
ll num_putss;ll a[maxn];
ll b[maxn];
int biaoji[maxn];
bool cmp(ll x,ll y)
{return x>y;
}
vector<int>v;bool check(int mid)
{for(int i=0; i<mid; i++)a[i]=b[i];int number=mid;for(int i=0; i<k-1; i++){for(int j=0; j<mid; ++j){while(number<n&&b[number]<a[j]*2) number++;if(number==n) return 0;a[j]=b[number];number++;}}return 1;
}int main()
{int T,casee=1;cin>>T;while(T--){scanf("%d%d",&n,&k);for(int i=0; i<n; ++i){scanf("%lld",&b[i]);}if(k==1){printf("Case #%d: ",casee++);cout<<n<<endl;continue;}sort(b,b+n);int l=0,r=n/k;while(l<r){int mid=(l+r+1)/2;if(check(mid)){l=mid;}else{r=mid-1;}}printf("Case #%d: ",casee++);cout<<l<<endl;}return 0;
}

 

本文标签： G

版权声明：本文标题：G 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1693752893h240793.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。