BAEKJOON 2792 - LJUBOMORA

문제: https://www.acmicpc.net/problem/2792

문제

A marble factory has donated a large box of marbles to a kindergarten. Each marble has one out of M different colours. The governess needs to divide all the marbles between the N children in her group. It is acceptable if some children don't get any marbles. However, no child wants marbles of different colours – in other words, all marbles that a child gets need to be the same colour.

The governess also knows that children will be jealous if a child gets too many marbles. As an approximation, we will define the envy level in the group as the largest number of marbles given to one child. Help the governess divide the marbles in order to minimize the envy level.

For example, if the box contains 4 red marbles (RRRR) and 7 blue marbles (BBBBBBB) which we have to divide between 5 children, we can achieve an envy level of 3 by dividing the marbles in the following way: RR, RR, BB, BB, BBB. This is the lowest achievable envy level.

입력

The first line of input contains two positive integers, N (1 ≤ N ≤ 109), the number of children, and M (1 ≤ M ≤ 300 000, M ≤ N), the number of different colours.

Each of the following M lines contains a positive integer from the interval [1, 109], with the integer in line K denoting the number of marbles with colour K.

출력

The first and only line of output should contain the minimum possible envy level.

 

예제 입력 

5 2
7
4

예제 출력 

3

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #1 4번

앞선 최소값을 찾는 이진 탐색 문제들과 같은 방법으로 풀 수 있는 문제입니다. 단, 해당 mid 값이 유효한 값인지 찾는 함수를 잘 만들어야 시간 초과를 피할 수 있습니다. 

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
using namespace std;
typedef long long ll;
 
bool canDivide(vector<int> colors, ll mid, int n)
{
    ll count = 0;
    for (auto& e : colors)
    {
        while (true)
        {
            ll division = min(mid, (ll)e);
            if (division == 0)
                break;
            ll quotient = e / division;
            if (quotient > 0)
            {
                count += quotient;
                if (count > n)
                    return false;
                e -= quotient * division;
            }
        }
    }
    return true;
}
 
int binarySearch(vector<int>& colors, ll high, int n)
{
    ll low = 1;
    ll ret = high;
 
    while (low <= high)
    {
        ll mid = (low + high) / 2;
        if (!canDivide(colors, mid, n))
        {
            low = mid + 1;
        }
        else
        {
            ret = min(ret, mid);
            high = mid - 1;
        }
    }
    return ret;
}
 
int main()
{
    int n, m, highest;
    highest = 0;
    scanf("%d %d", &n, &m);
    vector<int> colors(m, 0);
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &colors[i]);
        highest = max(highest, colors[i]);
    }
 
    printf("%d\n", binarySearch(colors, highest, n));
 
    return 0;
}