Q2. Minimum K to Reduce Array Within Limit

📘 題目敘述

你會得到一個正整數陣列 nums。

對於一個正整數 k，定義 nonPositive(nums, k) 為：把 nums 裡每個元素都變成 非正數（<= 0） 所需要的最少操作次數。

每一次操作中，你可以選一個 index i，並把 nums[i] 減少 k。

請回傳最小的 k，使得 nonPositive(nums, k) <= k^2。

條件限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

🧠 解題思路

這題核心是「二分搜尋答案 k」。

先看固定一個 k 時，要把每個 nums[i] 減到 <= 0，最少需要幾次操作：

• 每次減 k
• 需要的次數就是 ceil(nums[i] / k)

所以總操作次數：

nonPositive(nums, k) = Σ ceil(nums[i] / k)

而題目要的是：

Σ ceil(nums[i] / k) <= k^2

為什麼可以二分搜？

因為 k 越大，每次減得越多，ceil(nums[i] / k) 就越小或不變，所以整個總和也只會變小或不變。

• 如果某個 k 已經可以達成條件，那更大的 k 一定也可以。
• 這是一個可行性單調問題，所以可以二分搜最小可行 k。

怎麼算 ceil(nums[i] / k)？

用整數除法技巧：

ceil(a / b) = (a + b - 1) / b

所有變數

• l, r：二分搜尋的左右界。
• k：目前二分搜測試的候選值。
• count：總操作次數（也就是 nonPositive(nums, k)）。

🪜 主要流程步驟

1. 設定二分搜尋範圍

• l 是合理下界（從 ceil(sqrt(n)) 開始）。
• r 是上界（用 max(max(nums), n) 保證足夠大）。

2. 用二分搜測試 k 是否可行

• 計算 count = Σ ceil(nums[i] / k)。
• 如果 count <= k^2，縮小右界 r = k。
• 否則增大左界 l = k + 1。

3. 收斂後回傳答案

• 當 l == r 時回傳 l。

💻 程式碼實作

class Solution {
public:
    int minimumK(vector<int>& nums) {
        int l = static_cast<int>(ceil(sqrt(nums.size())));
        int r = nums.size();
        for (int t : nums) {
            r = max(t, r);
        }
        while (l < r) {
            long long k = (l + r) / 2;
            long long count = 0;
            for (int i = 0; i < static_cast<int>(nums.size()); i++) {
                count += (nums[i] + k - 1) / k;
            }
            if (count <= k * k) {
                r = static_cast<int>(k);
            } else {
                l = static_cast<int>(k) + 1;
            }
        }
        return l;
    }
};

🔗 題目連結

https://leetcode.com/contest/biweekly-contest-175/problems/minimum-k-to-reduce-array-within-limit/