Find the Smallest Divisor Given a Threshold หาตัวหารน้อยที่สุดใน C++

ให้อาร์เรย์ nums และ threshold k หาตัวหารบวกน้อยที่สุดที่ทำให้ผลรวม ceil(nums[i]/divisor) ≤ k

ตัวอย่าง: nums=[1,2,5,9], k=6 → divisor=5 (ผลรวม: 1+1+1+2=5 ≤ 6)

วิธีแก้ปัญหา (Binary Search)

1. ฟังก์ชัน check(x): คำนวณผลรวม ceil(nums[i]/x) คืน true ถ้า ≤ k
2. Binary search: low=1, high=1e7
   • mid = (low+high)/2
   • ถ้า check(mid) → high = mid มิฉะนั้น low = mid+1
3. คืนค่า high

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool ok(int x, vector<int>& nums, int th) {
        int sum = 0;
        for (int v : nums) sum += ceil((double)v / x);
        return sum <= th;
    }
    
    int smallestDivisor(vector<int>& nums, int th) {
        int low = 1, high = 1e7;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, nums, th)) high = mid;
            else low = mid + 1;
        }
        return high;
    }
};

int main() {
    vector<int> v = {1,2,5,9};
    Solution ob;
    cout << ob.smallestDivisor(v, 6);
    return 0;
}

Input

[1,2,5,9] 6

Output

5