3824. 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
要讓 nums[i] 從正數變成 <= 0，需要做的次數就是 ceil(nums[i] / k)

所以總操作次數：

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

而題目要的是：

找最小的 k，讓 Σ ceil(nums[i] / k) <= k^2

為什麼可以二分搜？

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

換句話說：

如果某個 k 已經可以達成 Σ ceil(nums[i] / k) <= k^2 那更大的 k 一定也可以（更容易達成）
這是一個典型的「可行性單調」問題，所以可以二分搜最小可行 k

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

用整數除法技巧：

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

所以這題就是：

count += (nums[i] + k - 1) / k

最後檢查：

count <= k * k 代表 k 可行
不然就代表 k 太小

所有變數

l, r：二分搜尋的左右界（答案一定落在這個範圍內）
k：目前二分搜測試的候選值
count：對這個 k 計算出來的總操作次數（也就是 nonPositive(nums, k)）

🪜 主要流程步驟

1. 設定二分搜尋範圍

你先設定一個答案範圍 [l, r]：

l 是你認為合理的下界（從 ceil(sqrt(n)) 開始）
r 是上界，確保一定夠大（你用 max(max(nums), n) 來當上界）

這樣就能保證答案一定在區間內。

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

每次取中間值 k 後，計算 count = Σ ceil(nums[i]/k)：

對每個 nums[i]，它至少要被減 ceil(nums[i]/k) 次才會變成 <= 0
把所有元素需要的次數加起來就是 count

接著用題目條件判斷：

如果 count <= k^2，代表 k 已經夠大，答案可能更小 所以把右界縮到 r = k
如果 count > k^2，代表 k 太小，必須增大 k 所以把左界移到 l = k + 1

因為可行性是單調的，所以這樣縮範圍一定不會漏掉答案。

3. 收斂後回傳答案

當 l == r 時，代表已經找到最小可行 k，回傳 l。

💻 程式碼實作

class Solution {
public:
    int minimumK(vector<int>& nums) {
        int l = ceil(sqrt(nums.size())), 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 < nums.size(); i++) {
                count += (nums[i] + k - 1) / k;
            }
            if (count <= k * k) {
                r = k;
            } else {
                l = k + 1;
            }
        }
        return l;
    }
};

🔗 題目連結

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