P7585 [COCI2012-2013#1] LJUBOMORA 题解

信息向阳花木

2021-08-28 15:30:05

Solution

~~话说为什么要嫉妒别人,太小心眼了吧。。。~~ ### 简化题意! 有 $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; } ```