1654-ローカルエリアネットワークのクリップ-二分探索

質問する

質問リンク:https://www.acmicpc.net/problem/1654

ポリシー

は,我々が要求するローカルエリアネットワーク線の最大長を二分探索で求めた.

は、選択した長さごとにgetNumberOfLineという関数をそれぞれ作成し、その長さがどれだけ作成できるかを求める必要があります.

個の数が同じかそれ以上であれば、長さを増やし、少なければ長さを減らすべきだ.

コード#コード#

#include<bits/stdc++.h>

using namespace std;

int N, K;
vector<int> a;

//// 문제에서 lt, rt, 그리고 최대값 m까지 long long으로 받아야 답이 해결된다.
//// 바보같이 최대값이 2147000000이지만 이는 2^32보다 작은값이다... 하지만 문제에서 mid를 계산할때
//// int형의 범위를 넘어버린다. 따라서 lt와 rt도 long long으로 해주어야한다 . 

long long getNumberOfLine(int num, int length){
    long long cnt = 0;
    // 0보다 크다가 아니라 크거나 같다이다.... 여기서 문제 틀림
    while(num-length >= 0){
        cnt++;
        num = num-length;
    }
    return cnt;
}
int res = 0;
int BinarySearch(long long lt, long long rt){
    if(lt > rt){
        return res;
    }
    else{
        
        long long mid = (lt+rt) / 2;

        long long numOfLine = 0;
        for(int i=0; i<N; i++){
            numOfLine += getNumberOfLine(a[i], mid);
        }

        /// 항상 정확히 필요한 부분까지만 하면 되는거라고 생각했지만 N개보다 더 많이 만드는것도 N개를 만드는것에 포함된다. 
        if(numOfLine >= K){
            if(mid > res){
                
                res = mid;
            }
            return BinarySearch(mid+1, rt);
        }
        else {
            return BinarySearch(lt, mid-1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);

    cin >> N >> K;
    int tmp;
    int m = 0;
    for(int i=0; i<N; i++){
        cin >> tmp;
        a.push_back(tmp);
        if(tmp > m ) m = tmp;
    }

    cout<<BinarySearch(1, m) << endl;
    return 0;
}

感想

問題の核心的な考えは分かっているが、中間ミスが多すぎて、少しためらっている.まずはよくlong longを使うときは必ず書きます後ろにはミスの問題がたくさんあります...必ずlong longを使うときに使いますnumOfLine>=Kでres値を変更する必要がある非常に重要な部分もあります.最初はnumOfLine=Kでしか交換していませんでしたが、入力法によっては対応する条件で答えが見つからないかもしれません.つまりK=3ですがnumofLineは4としか表示されない場合があります.
この問題から多くのことを学んだ.
1. long long
2. numOfLine >= K