algo-aha

猴子吃香蕉的最小吃速

• https://leetcode.com/problems/koko-eating-bananas/

int minEatingSpeed(vector<int>& piles, int H) {
    int lo = 1, hi = 1e9;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (enough(mid, piles, H)) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

bool enough(int K, vector<int> &piles, int H) {
    // 吃完piles[i]需要(piles[i]+K-1)/K小时
    // sum{ (piles[i]+K-1)/K }是K的递减函数，
    // sum<=H 符合二分搜索[0 0 .. 0 1 1 ..]的条件
    int sum = 0;
    for (int pile : piles) {
        sum += (pile + K - 1) / K;
    }
    return sum <= H;
}

D天内运完的最小运力

• https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

int shipWithinDays(vector<int>& weights, int D) {
    int maxW = 0, sumW = 0;
    for (int w : weights) {
        maxW = max(maxW, w);
        sumW += w;
    }

    int l = maxW, u = sumW;
    while (l <= u) {
        int m = l + (u - l) / 2;
        if (enough(m, weights, D)) {
            u = m - 1;
        } else {
            l = m + 1;
        }
    }
    return l;
}

bool enough(int capacity, vector<int>& weights, int D) {
    // 运载力capacity、天数days的关系
    int weight = 0, days = 1;
    for (int i = 0; i < weights.size(); i++) {
        weight += weights[i];
        if (weight > capacity) {
            days++;
            weight = weights[i];
        }
    }
    // capacity越大、days越小、days<=D越返回1
    return days <= D;
}

各子段和的最大值最小化

• https://leetcode.com/problems/split-array-largest-sum

int splitArray(vector<int>& nums, int m) {
    // 各子段和的最大值x在值范围[max(nums), sum(nums)]
    int mx = 0;
    long sum = 0;
    for (int num : nums) {
        mx = max(mx, num);
        sum += num;
    }

    // 二分搜素猜子段和的最大值x
    long l = mx, u = sum;
    while (l <= u) {
        long mid = l + (u - l) / 2;
        if (enough(mid, nums, m)) {
            u = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l;        
}

bool enough(long x, vector<int> &nums, int m) {
    // 子段和的最大值x和子段数m的关系，是关于x的递减函数count(x)
    // 条件式count(x)<=m满足二分搜索的条件形式[0 0 ... 0 1 1 ...]
    int count = 1;
    long sum = 0;
    for (int num : nums) {
        sum += num;
        if (sum > x) {
            count++;
            sum = num;
            if (count > m) return false;
        }
    }
    return true;
}

制造花束的最小等待天数

• https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets

int minDays(vector<int>& bloomDay, int m, int k) {
    // 要在bloomDay中找出m个k长的子段
    if (bloomDay.size() < m * k) return -1;
    // 等待天数wait为各子段最大值的最小值，值范围[min(bloomDay),max(bloomDay)]
    int mn = INT_MAX, mx = INT_MIN;
    for (int day : bloomDay) {
        mn = min(mn, day);
        mx = max(mx, day);
    }
    
    // 二分搜索猜等待天数
    int lo = mn, hi = mx;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (enough(mid, bloomDay, m, k)) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

bool enough(int wait, vector<int>& bloomDay, int m, int k) {
    // 等待天数wait一确定，bloomDay根据开没开花变成10数组，
    // 就能统计有多少个k长的连续1的子段，count(wait)是关于wait的递增函数，
    // count(wait)>=m满足二分搜索的条件形式[0..0 1 1..]
    int adjacent = 0, count = 0;
    for (int day : bloomDay) {
        if (day <= wait) {
            adjacent++;
            if (adjacent >= k) {
                count++;
                adjacent = 0;
            }
        } else {
            adjacent = 0;
        }
    }
    return count >= m;
}

使放小球的位置尽可能分散

• https://leetcode.com/problems/magnetic-force-between-two-balls/

int maxDistance(vector<int>& position, int m) {
    // 在允许的不同位置放球，使它们尽可能分散
    // 最小距离dist的取值在[1..position[-1]-1]
    // 二分搜索猜dist，找满足条件最后一个，修改标准二分搜索写法：
    // 1. 条件式中去掉等号，2. 最终要找的位置为lo
    sort(position.begin(), position.end());
    int lo = 0, hi = position.back();
    int ans = 0;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (enough(mid, position, m)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    return lo; // 修改2
}

bool enough(int dist, vector<int>& position, int m) {
    // 两球间的最小距离dist一确定，position[]中能放的球数count也确定
    // count(dist)是关于dist的递减函数，
    // count(dist)<m符合二分搜索的条件形式[0..0 1 1..]，
    // 用<m而不是<=m，因为要找满足条件的最后一个，条件式中去掉等号
    const int N = position.size();
    int nextPos = 0, count = 0;
    for (int i = 0; i < N; i++) {            
        if (position[i] >= nextPos) {
            count++;
            nextPos = position[i] + dist;
        }
    }
    return count < m; // 修改1
}

将>=value的全改成value，使数组之和最接近target的最小value

• https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/

int findBestValue(vector<int>& arr, int target) {
    const int N = arr.size();
    sort(begin(arr), end(arr));
    vector<int> presum(N + 1, 0); // presum[i]表示sum(arr[0..i))
    int mx = INT_MIN;
    for (int i = 0; i < N; i++) {
        presum[i+1] = presum[i] + arr[i];
        mx = max(mx, arr[i]);
    }
    
    int l = 0, u = mx + 1; // 题目条件
    while (l + 1 < u) {
        int m = l + (u - l) / 2;
        // 满足二分搜索的条件形式[0..0 1..1]
        if (getSum(m, arr, presum) >= target) {
            u = m;
        } else {
            l = m;
        }
    }
    // 找最接近target的数，u和u-1作为候选
    int diff1 = abs(getSum(u, arr, presum) - target);
    int diff2 = abs(getSum(u-1, arr, presum) - target);
    return diff2 <= diff1 ? u-1 : u;
}

int getSum(int value, vector<int>& arr, const vector<int> &presum) {
    // 将>=value的值全变成value
    int idx = lower_bound(begin(arr), end(arr), value) - begin(arr);
    // [0..idx)为原数，[idx..N)变为value，sum(value)是关于value的递增函数
    int sum = presum[idx] + (arr.size() - idx) * value;
    return sum;
}