273. MinMaxDivision

10696 ワード
アルゴリズム#アルゴリズム# テキストリンク

  • 二分化の対象を探さなければなりません.この問題は結果を二つに分けるべきだ.
  • kブロック内の最大アレイの合計の最小値.

  • 0を和で割った後の二分法の判断条件

  • アレイをk個以下のブロックに分割できるかどうか

  • 各ブロックの和は、等しいか等しいか以下です.

  • 条件を満たすとmid値が大きすぎて小さくなる可能性があります.

    • 1. JavaScript

    
function solution(K, M, A) {
    let begin = A.reduce((a, v) => (a + v), 0);
    begin = parseInt((begin+K-1)/K);
    let max = Math.max(A);
    if (max > begin) begin = max;

    let end = begin + M + 1;
    let res = 0;

    while(begin <= end) {
        let mid = (begin + end) / 2;
        let sum = 0;
        let block = 1;
        for (let ind in A) {
            let a = A[ind];
            sum += a;
            if (sum > mid) {
                ++block;
                if (block > K) break;
                sum = a;
            }
        }
        if (block > K) {
            begin = mid + 1;
        } else {
            res = mid;
            end = mid - 1;
        }
    }
    return res;
}

    2. Python

    

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def isValid(A, cnt, size):
    b_sum = 0
    b_cnt = 0

    #블럭 최대값 넘으면 블럭 나누기
    for i in A:
        if b_sum + i > size:
            b_sum = i
            b_cnt += 1

        else:
            b_sum += i
        
        if b_cnt >= cnt:
            return False
    return True
    
def solution(K, M, A):
    # write your code in Python 3.6
    cnt = K
    left = max(A)
    right = sum(A)

    if cnt == 1:
        return right
    if cnt >= len(A):
        return left
    
    while(left <= right):
        mid = (left + right) // 2
        if isValid(A, cnt, mid):
            right = mid - 1
        else:
            left = mid + 1

    return left
    2つの数字を比較(1330)
    JavaScript #9 ~ if/else Statements