랜선 자르기 C++ - 백준 1654

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

이 문제는 parametric search를 사용해 푸는 문제이다.

랜선 길이마다의 몫을 구해서 그때 마다 이분탐색을 했다.

long long을 사용하지 않아서 조금 애먹었다.

코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#define MAX_LENGTH 10000000000
#define MAX_LINES 10000
typedef long long ll;
using namespace std;

ll lines[MAX_LINES];
ll n;
ll k;
ll ans=0;
int main(){
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> k >> n;
    for(int i=0;i<k;i++){
        cin >> lines[i];
    }
	ll s=1;
	ll e=MAX_LENGTH;
	while(s<=e){
		ll mid=(s+e)/2;
		ll cnt=0;
		for(int i=0;i<k;i++){
			if(lines[i]>=mid) cnt+=lines[i]/mid;
		}
		if(cnt<n){
			e=mid-1;
		}
		else{
			ans=max(ans,mid);
			s=mid+1;
		}
	}
	cout << ans;
}