Tìm ước số nhỏ nhất cho ngưỡng (Find the Smallest Divisor Given a Threshold) trong C++

Cho mảng nums và ngưỡng k. Tìm ước số dương nhỏ nhất d sao cho tổng ceil(nums[i]/d) ≤ k.

Ví dụ: nums=[1,2,5,9], k=6 → d=5 (tổng = 1+1+1+2=5).

Thuật toán (Tìm kiếm nhị phân)

1. Hàm check(d): tính tổng ceiling chia cho d, so với k.
2. Binary search d trong [1, 1e7]. Nếu check(mid) true → high=mid, else low=mid+1.

Mã nguồn C++

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

class Solution {
    bool ok(int x, vector& nums, int th) {
        int sum=0;
        for (int v : nums) sum += (v + x - 1) / x; // ceil
        return sum <= th;
    }
public:
    int smallestDivisor(vector& 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 v = {1,2,5,9};
    Solution ob;
    cout << ob.smallestDivisor(v, 6); // 5
    return 0;
}

Đầu vào / Đầu ra

Input: [1,2,5,9] 6

Output: 5