백준 16766번 Convention

백준 16766번 Convention

#include <iostream>
#include <string>
#include<cstring>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int hi = 1000000000;
 
int N, M, C;
int arr[111111];
bool CanRide(int x) {
    int cnt = 1;
    for (int i = 1, start = 0; i < N; i++) {
        //arr[start]+x는  도착한 버스를 처음타는 소의 기다리는 시간
        if (i - start < C&& arr[i] <= arr[start] + x)continue;
        //버스탑승인원초과하거나 x초 대기시간 넘으면
        //버스보내고 다른버스태운다.
        cnt += 1;
        start = i;
    }
 
    return cnt <= M;
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int lo = 0;
    cin >> N >> M >> C;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    sort(arr, arr + N);
 
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        //최대 mid 초안에 모든 소들이 탑승 가능한지? 
        if (CanRide(mid))
            hi = mid-1;
        else
            lo = mid+1;
    }
    cout << lo;
 
    return 0;
}
 

출처:https://www.acmicpc.net/problem/16766

문제는 

N마리의 소를 M개의 버스로 버스의 정원은 C! 

조건 만족하는 최대 대기시간중에 최소 시간을 구해보자! 입니다.

MC>=N인것에 주의를 해주셔야됩니다. 꼭 버스정원을 꽉 채워서 소를 보낼 필요가 없어요!

2 2 2

10 210

0

이런식인 거죵  

이분 탐색으로 문제를 풀 생각을 못했는데 같은 학회원 알고리즘고수님께서 이분탐색으로 쉽게 푸셨네요. 코드 참조해서 

올렸습니다.