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

Question

村里有一所学校。它有 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

Answer 1

应用二进制搜索来找到最小数量的学生/蛋糕。 将下限“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;
}