BOJ1654:Lansun Cutting-C++


ローカルエリアネットワークのクリップ



コード#コード#

#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]);
    }
    /* left가 0이면 N=1,K=1, input=1 일 때 나누는 수인 mid가 0이되어서
        런타임 에러가 발생한다 */
    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; // 항상 mid가 0이되는 예외가 없는지 확인해줘야 함
        if(tot < M)
            right = mid - 1;
        else
        /* tot이 M보다 크거나 같을때 일단 지금까지 랜선 길이를 저장하고
           더 큰값을 검사하러 이동 */
        {
            ans = max(ans,mid);
            left = mid + 1;
        }
    }
    cout << ans;
    return 0;
}
  • 論理
    :検索최적의 랜선 길이のナビゲーション이분탐색

  • :이분탐색をする時、よく나누는 수人のmidを探して0이되는 경우を探して、예외처리をします
    (本問題
    :N=1, M=1, input=1の場合、mid0であるため、최초left1)
  • に初期化する.