2792번 보석 상자

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

이분 탐색 문제이다.

핵심은 total이 N보다 작거나 같으면 right = mid - 1로 통해

계속해서 mid를 작게 한다.

문제에서 어차피 모두에게 나눠주지 않아도 된다고 하였기 때문이다.

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M;
 
vector<int> v;
 
int bs(int left, int right)
{
    int ret = 2e9;
 
    while (left <= right) {
        int mid = (left + right) / 2, total = 0;
 
        for (auto i : v) {
            total += i / mid;
            if (i%mid) ++total;
            if (total > N) break;
        }
 
        if (total <= N) ret = min(ret, mid), right = mid - 1;
        else left = mid + 1;
    }
 
    return ret;
}
 
int main(void)
{
    int c, answer = 0;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++){
        scanf("%d", &c);
        v.push_back(c);
    }
 
    sort(v.begin(), v.end());
 
    printf("%d\n", bs(1, *max_element(v.begin(), v.end())));
 
    return 0;
}