Tìm số chia nhỏ nhất cho một ngưỡng trong C ++

Giả sử chúng ta có một mảng các số nguyên gọi là num và một số nguyên k, đó là giá trị ngưỡng, chúng ta sẽ chọn một ước số nguyên dương và chia tất cả mảng cho nó và tính tổng kết quả của phép chia. Chúng ta phải tìm ước số nhỏ nhất sao cho kết quả đề cập ở trên nhỏ hơn hoặc bằng giá trị ngưỡng k. Ví dụ - nếu nums =[1,2,5,9] và k =6, thì đầu ra sẽ là 5. Chúng ta có thể nhận được tổng là (1 + 2 + 5 + 9) =17 khi số chia là 1. Nếu số chia là 4 thì ta có tổng 7 là (1 + 1 + 2 + 3), khi số chia là 5 thì tổng sẽ là (1 + 1 + 1 + 2) =5

Đảm bảo rằng sẽ có câu trả lời.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• xác định một phương thức được gọi là kiểm tra, phương thức này sẽ nhận ba tham số như x, array nums và k, điều này sẽ như sau -
• sum:=0
• cho tôi trong phạm vi từ 0 đến kích thước của nums - 1
  • sum:=sum + giá trị trần của nums [i] / x
• trả về true, nếu sum <=k, ngược lại là false
• Phương pháp thực tế sẽ giống như bên dưới -
• đặt thấp:=1 và cao:=inf
• trong khi thấp
• giữa:=low + (cao - thấp) / 2
• nếu kiểm tra (giữa, nums, k) thì cao:=giữa, ngược lại thấp:=giữa + 1

• Hãy cho chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[1,2,5,9]
6

Đầu ra

5