maximum-number-of-upgradable-servers.cpp

// Time:  O(n)
// Space: O(1)

// math
class Solution {
public:
    vector<int> maxUpgrades(vector<int>& count, vector<int>& upgrade, vector<int>& sell, vector<int>& money) {
        const auto& ceil_divide = [](const auto& a, const auto& b) {
            return (a + b - 1) / b ;
        };

        // let x be the number of sold servers
        // (c-x)*u <= m+(x*s)
        // x >= (c*u-m)//(u+s) <= 0
        // c-x <= c-(c*u-m)//(u+s) <= c
        vector<int> result(size(count));
        for (int i = 0; i < size(count); ++i) {
            result[i] = min(count[i] - ceil_divide(static_cast<int64_t>(count[i]) * upgrade[i] - money[i], upgrade[i] + sell[i]), static_cast<int64_t>(count[i]));
        }
        return result;
    }
};