文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

描述

給你一個整數數組 nums 和一個正整數 threshold ，你需要選擇一個正整數作為除數，然后將數組里每個數都除以它，并對除法結果求和。

請你找出能夠使上述結果小于等于閾值 threshold 的除數中 最小 的那個。

每個數除以除數后都向上取整，比方說 7/3 = 3 ， 10/2 = 5 。

題目保證一定有解。 1 <= nums.length <= 5 * 10^4 1 <= nums[i] <= 10^6 nums.length <= threshold <= 10^6示例 1： 輸入：nums = [1,2,5,9], threshold = 6 輸出：5 解釋：如果除數為 1 ，我們可以得到和為 17 （1+2+5+9）。 如果除數為 4 ，我們可以得到和為 7 (1+1+2+3) 。 如果除數為 5 ，和為 5 (1+1+1+2)。示例 2： 輸入：nums = [2,3,5,7,11], threshold = 11 輸出：3示例 3： 輸入：nums = [19], threshold = 5 輸出：4

https://www.lintcode.com/problem/find-the-smallest-divisor-given-a-threshold/description

2. 解題

類似題目：
LeetCode 410. 分割數組的最大值（極小極大化 二分查找）
LeetCode 668. 乘法表中第k小的數（二分查找）
LeetCode 774. 最小化去加油站的最大距離（極小極大化 二分查找）
LeetCode 875. 愛吃香蕉的珂珂（二分查找）
LeetCode LCP 12. 小張刷題計劃（二分查找）
LeetCode 1011. 在 D 天內送達包裹的能力（二分查找）
LeetCode 1102. 得分最高的路徑（優先隊列BFS/極大極小化 二分查找）
LeetCode 1062. 最長重復子串（二分查找）
LeetCode 5438. 制作 m 束花所需的最少天數（二分查找）
LeetCode 5489. 兩球之間的磁力（極小極大化 二分查找）
LeetCode 5548. 最小體力消耗路徑（DFS + 二分查找）

• 二分查找答案，除數變大，和變小或不變，有單調性

class Solution { public:/*** @param nums: an array of integers* @param threshold: an integer* @return: return the smallest divisor*/int smallestDivisor(vector<int> &nums, int threshold) {// write your code hereint l = 1, r = INT_MAX, mid, ans;while(l <= r){mid = l+((r-l)>>1);if(sumok(nums, mid, threshold)){ans = mid;r = mid-1;}elsel = mid+1;}return ans;}bool sumok(vector<int>& a, int div, int threshold){long long sum = 0;for(auto n : a){sum += ceil(n/double(div));if(sum > threshold)return false;}return true;} };

53ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LintCode 1816. 使结果不超过阈值的最小除数（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。