#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
int a;
cin >> a;
arr.push_back(a);
high=max(high,arr[i]);
}
ll left=1, right=high;
ll ans=0;
while(left<=right)
{
ll tot = 0;
ll mid = (left + right)/2;
for(auto a : arr)
tot += a/mid;
if(tot < M)
right = mid - 1;
else
{
ans = max(ans,mid);
left = mid + 1;
}
}
cout << ans;
return 0;
}
- 로직
: 최적의 랜선 길이
를 찾는 탐색을 이분탐색
으로 하여 찾는다
- 주의
: 이분탐색
을 할 때 항상 나누는 수
인 mid
가 0이되는 경우
를 찾아 예외처리
를 해주어야 한다
(본 문제
: N=1, M=1, input=1
일 때 mid
가 0
이되므로 최초left
를 1
로 초기화)