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になります

答えがあることが保証されています。

これを解決するには、次の手順に従います-

• チェックと呼ばれる1つのメソッドを定義します。これは、x、配列番号、kなどの3つのパラメーターを取ります。これは、次のようになります-
• 合計：=0
• 0からnumsのサイズまでの範囲のiの場合– 1
  • sum：=sum + nums [i]/xの上限値
• 合計が<=kの場合はtrueを返し、それ以外の場合はfalseを返します
• 実際の方法は以下のようになります-
• 低：=1および高：=infに設定
• 低い<高い
  • 中：=低+（高–低）/ 2
  • check（mid、nums、k）の場合、high：=mid、それ以外の場合はlow：=mid + 1
• ハイに戻る

• 理解を深めるために、次の実装を見てみましょう-

例

#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