P7585 [COCI2012-2013#1] LJUBOMORA 题解

fanypcd · 2021-05-31 23:50:48 · 题解

题目简述：

有 M 种不同颜色的弹珠，第 i 种颜色的弹珠有 x_i 个。现在要求将弹珠分成 N 份（全部用完），且每份颜色相同，并使得弹珠数量最多的那一份尽可能少（即嫉妒值最小）。

题目思路：

• 二分（这种最大中取最小，最小中取最大的且不方便直接求解的问题一般都用二分答案，然后验证答案的合法性）
• 考虑枚举可能的嫉妒值,初始范围 l,r 是 [0,x_{max}]。
• 每次取 mid = (l+r) / 2，若满足条件（全部用完），则令 r=mid （保留结果），否则令 l=mid+1（ mid 不合法则舍弃）。
• 验证过程则是贪心，即对于第 i 种颜色的弹珠，至少要分给 (x_i+mid - 1)/mid 人，这样可以规避不整除人数加一的情况（实际代码中使用特判）。
• 如果总人数 tot\leq N，则 mid 作为嫉妒值是可以满足的（允许有人分不到，所以可以小于），反之不能满足。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, a[300005];
int check(int x)
{
    int tot = 0;
    for(int i = 1; i <= m; i++)
    {
        tot += a[i] / x;
        if(a[i] % x)//此时该种颜色的弹珠无法分完，剩下的还需要分给一个人
        {
            tot++;
        }
    }
    return tot <= n;
}
int main()
{
    ios::sync_with_stdio(false);//读入优化
    cin >> n >> m;
    int l = 0, r = -1, mid;
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i];
        r = max(r, a[i]);
    }
    while(l < r)
    {
        mid = (l + r) / 2;
        if(check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l;
    return 0;
}