# L14-MinMaxDivision
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/
## Key
1. ~~這題本來想用二分查找找最大值元素，區塊數K範圍很大、可能有很多接近最大值M的數在原陣列中，所以不知道怎麼下手...~~
2. 其實直接可以假設最小的最大區塊和值就是一個平均(最小值是最大值元素，最大值是陣列總和，兩者的平均)

3. 再用這個平均去反推block數，如果累加過程大於最大值，代表超過一個block了，count就加一，以此類推，算出block數

4. 接著使用二分查找，將算出的block數和K比較，如果太小，代表設定的平均太大，要縮小才能讓block數縮小，所以將最大值改為平均-1；反之，算出的block數太大，就是平均太小，所以將最小值改為平均+1

5. 這種沒有明確目標或範圍時，使用二分查找就比較困難
## Reference
## Solution

#include <algorithm>

int getBlockNumber(vector<int> &A, int blockTotal) {
    int size = A.size(), total = 0, count = 0;
    for (int i = 0; i < size; i++) {
        total += A[i];
        if (total > blockTotal) {
            total = A[i];
            count += 1;
        }
    }
    
    return count + 1;
}

int solution(int K, int M, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int sum = 0, size = A.size();
    for (int i = 0; i < size; i++) {
        sum += A[i];
    }
    
    if (K == 1) {
        return sum;
    } else {
         int minTotal = *max_element(A.begin(), A.end()), maxTotal = sum;
            while (minTotal <= maxTotal) {
                int testTotal = int((minTotal + maxTotal) / 2);
                int testBlockNum = getBlockNumber(A, testTotal);
                if (testBlockNum <= K) {
                    maxTotal = testTotal - 1;
                } else {
                    minTotal = testTotal + 1;
                }
            }
            return minTotal;
    }
}