algorithm - 在N个类(class)之间划分B个奶酪蛋糕，以最大程度地减少每个蛋糕的最大学生人数

村里有一所学校。它有N个班一个晴朗的日子，有人给学校捐赠了蓝莓奶酪蛋糕。现在你需要把这些蛋糕分成：
每个班至少有一个蛋糕。
每个班级将在学生中分享蛋糕。
你的目标是尽量减少每个班级学生每蛋糕最多的学生人数。
输入
包含两个空格分隔的整数n和b，分别表示蓝莓奶酪蛋糕的类数和总数。
接下来的N行包含每个班级的学生人数。
输出
对于每个测试用例，输出共享蛋糕的学生的最大数量。
约束条件
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”为任何给定班级的最大学生数。
让“mid”表示当前学生/蛋糕，其中mid=（l+u）/2，然后，
计算每个中值所需的蛋糕数量'req'，
如果需求应用二进制搜索。
当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;
}