資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中查詢給定閾值的最小除數
假設我們有一個名為 nums 的整數陣列和一個整數 k（閾值），我們將選擇一個正整數除數並將陣列中的所有元素都除以它，然後將結果相加。我們必須找到最小的除數，使得上述結果小於或等於閾值 k。例如 - 如果 nums = [1,2,5,9] 且 k = 6，則輸出為 5。當除數為 1 時，我們可以得到總和 (1+2+5+9) = 17。如果除數為 4，則我們可以得到總和 7 為 (1+1+2+3)，當除數為 5 時，則總和為 (1+1+1+2) = 5。
保證會有一個答案。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個名為 check 的方法，它將接收三個引數，例如 x、陣列 nums 和 k，如下所示：
- sum := 0
- 對於 i 從 0 到 nums 的大小 - 1
- sum := sum + nums[i] / x 的上取整值
- 如果 sum <= k，則返回 true，否則返回 false
- 實際方法如下：
- 設定 low := 1 和 high := 無窮大
- 當 low < high
- mid := low + (high – low)/2
- 如果 check(mid, nums, k) 為真，則 high := mid，否則 low := mid + 1
- 返回 high
- 讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(int x, vector <int> &nums, int th){
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += ceil((double)nums[i]/(double)x);
}
return sum<=th;
}
int smallestDivisor(vector<int>& nums, int th) {
int low = 1;
int high = 1e7;
while(low < high){
int mid = low + (high - low)/2;
if(ok(mid, nums, th)){
high = mid;
}else low = mid + 1;
}
return high;
}
};
main(){
vector<int> v = {1,2,5,9};
Solution ob;
cout << (ob.smallestDivisor(v, 6));
}輸入
[1,2,5,9] 6
輸出
5
更新於：2020年5月2日
621 次瀏覽
廣告