gpt4 book ai didi

algorithm - 将 B 个芝士蛋糕分给 N 个类(class),以尽量减少每个蛋糕的最大学生人数

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:43:02 25 4
gpt4 key购买 nike

村里有一所学校。它有 N 个类。一个晴朗的日子,有人向学校捐赠了 B 蓝莓芝士蛋糕。现在你需要这样划分这些蛋糕:

每个类(class)至少得到 1 个蛋糕。每个类(class)将在学生之间分享蛋糕。您的目标是尽量减少任何类(class)中每个蛋糕的最大学生人数。

输入

包含两个空格分隔的整数 N 和 B,分别表示类数和蓝莓芝士蛋糕的总数。接下来的 N 行包含每个类(class)的学生人数。

输出对于每个测试用例,输出将分享蛋糕的学生的最大数量。约束条件2 <= N <= 5*10^5

N <= B <= 2*10^6 1 <= 第i类的学生人数 <= 5*10^6

样本输入 - 1 1 2 35 样本输出 - 1 18 样本输入 - 2 2 7 20 50 样本输出 - 2 10

最佳答案

应用二进制搜索来找到最小数量的学生/蛋糕。将下限“l”设为 1,将上限“u”设为任何给定类(class)的最大学生人数。令'mid'代表当前学生/蛋糕,其中mid=(l+u)/2,则,

计算每个中间值所需的蛋糕数量“req”,

如果 req<=蛋糕总数 u=mid-1 否则 l=mid+1。应用二进制搜索。

分别处理n>b的情况。链接到我针对此问题的 C++ 代码:https://ideone.com/zsTHC5

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n,b;cin>>n>>b;
ll arr[n],ans=0;
for(ll i=0;i<n;i++){cin>>arr[i];ans=max(ans,arr[i]);}

if(n>b)cout<<"-1";
else if(n==b)cout<<ans;
else // binary search to find minimum students/cake
{
ll l=1,r=ans,mid; // mid represents current number of students/cake
while(l<=r)
{
mid=(l+r)/2;
ll ct=0;
for(ll i=0;i<n;i++)
{
ct+=(arr[i]+mid-1)/mid;
}

if(ct<=b)
{
ans=min(ans,mid);
r=mid-1;
}
else
l=mid+1;
}
cout<<ans;
}

return 0;
}

关于algorithm - 将 B 个芝士蛋糕分给 N 个类(class),以尽量减少每个蛋糕的最大学生人数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40301019/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com