P7585 [COCI2012-2013#1] LJUBOMORA 题解

信息向阳花木 · 2021-08-28 15:30:05 · 题解

话说为什么要嫉妒别人，太小心眼了吧。。。

简化题意！

有 n 个小朋友，弹珠有 m 个颜色，每个小朋友分到的弹珠都得是同一种颜色的，求分到弹珠最多的小朋友手里的弹珠数最少是多少？

进入正题！

这道题用\color{red}{\text{二分}}去解决会比较好。我默认为你已经看过题了。

为什么用\color{red}{\text{二分}}比较好？

• 此题具有单调性。什么意思？就是说小朋友分到的弹珠越多，嫉妒值越高；小朋友分到的弹珠越少，嫉妒值越低。

所以，我们可以先用二分模板去\color{red}{\text{二分}}小朋友的嫉妒值，然后每次对于 mid 去调用 check 函数（check(mid)）。那么，check 函数该怎么写呢？

• 很简单，我们用求每个颜色按每个小朋友 mid 个弹珠，能分给多少个小朋友，用 sum 记按每个每个小朋友 mid 个弹珠最多能分给多少小朋友。若 sum>=n ，代表我们的嫉妒值得再大一些（小朋友的弹珠数量再大一些）；否则，需要把嫉妒值调小。

展示代码！

#include <iostream>  
using namespace std;
long long n,m,l=1,r,ans;
long long a[300010];
bool check(long long x){ //x 是当前的嫉妒值
    long long sum=0;
    for(int i=1;i<=m;i++) sum+=(a[i]+x-1)/x;
    return sum<=n;
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){cin>>a[i];r+=a[i];} //mid 的极限是总共的球数 
    while(l<r){ //二分模板 
        long long mid=(l+r)/2+1;
        if(check(mid)){r=mid-1;ans=mid;}
        else l=mid;
    }
    cout<<ans;
    return 0; 
}