跳转至

3155. 可升级服务器的最大数量 🔒

难度中等

题目描述

你有 n 个数据中心并且需要升级他们的服务器。

给定四个长度为 n 的数组 count，upgrade，sell 和 money，分别针对每个数据中心表示：

  • 服务器的数量
  • 升级单个服务器的成本
  • 出售服务器获得的钱
  • 你最初拥有的钱

返回一个数组 answer，其中对于每个数据中心，answer 中相应的元素代表可以升级的 最大 服务器数量。

请注意，一个数据中心的资金 不能 用于另一个数据中心。

 

示例 1：

输入：count = [4,3], upgrade = [3,5], sell = [4,2], money = [8,9]

输出：[3,2]

解释：

对于第一个数据中心，如果我们出售一台服务器，我们将会有 8 + 4 = 12 单位的钱并且我们能够升级其余的 3 台服务器。

对于第二个数据中心，如果我们出售一台服务器，我们将会有 9 + 2 = 11 单位的钱并且我们能够升级其余的 2 台服务器。

示例 2：

输入：count = [1], upgrade = [2], sell = [1], money = [1]

输出：[0]

 

提示：

  • 1 <= count.length == upgrade.length == sell.length == money.length <= 105
  • 1 <= count[i], upgrade[i], sell[i], money[i] <= 105

解法

方法一：数学

思考

每个机房可卖掉部分服务器筹资再升级其余。对升级台数 \(x\) 枚举到 \(count[i]\) 亦可，但机房数多时不如直接求解。

卖掉 \(count-x\) 台加上现金，须付 \(x\cdot upgrade\)。整理得 \(x\le(count\cdot sell+money)/(upgrade+sell)\)，且 \(x\le count\)。

对每个机房取该上界与台数的较小者。整数除法 naturally 向下取整。

对于每个数据中心，我们假设可以升级 \(\textit{x}\) 台服务器，那么 \(\textit{x} \times \textit{upgrade[i]} \leq \textit{count[i]} \times \textit{sell[i]} + \textit{money[i]}\)。即 \(\textit{x} \leq \frac{\textit{count[i]} \times \textit{sell[i]} + \textit{money[i]}}{\textit{upgrade[i]} + \textit{sell[i]}}\)。又因为 \(\textit{x} \leq \textit{count[i]}\)，所以我们取两者的最小值即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组的长度。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
class Solution:
    def maxUpgrades(
        self, count: List[int], upgrade: List[int], sell: List[int], money: List[int]
    ) -> List[int]:
        ans = []
        for cnt, cost, income, cash in zip(count, upgrade, sell, money):
            ans.append(min(cnt, (cnt * income + cash) // (cost + income)))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int[] maxUpgrades(int[] count, int[] upgrade, int[] sell, int[] money) {
        int n = count.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = Math.min(
                count[i], (int) ((1L * count[i] * sell[i] + money[i]) / (upgrade[i] + sell[i])));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    vector<int> maxUpgrades(vector<int>& count, vector<int>& upgrade, vector<int>& sell, vector<int>& money) {
        int n = count.size();
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            ans.push_back(min(count[i], (int) ((1LL * count[i] * sell[i] + money[i]) / (upgrade[i] + sell[i]))));
        }
        return ans;
    }
};

1
2
3
4
5
6
func maxUpgrades(count []int, upgrade []int, sell []int, money []int) (ans []int) {
    for i, cnt := range count {
        ans = append(ans, min(cnt, (cnt*sell[i]+money[i])/(upgrade[i]+sell[i])))
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maxUpgrades(
    count: number[],
    upgrade: number[],
    sell: number[],
    money: number[],
): number[] {
    const n = count.length;
    const ans: number[] = [];
    for (let i = 0; i < n; ++i) {
        const x = ((count[i] * sell[i] + money[i]) / (upgrade[i] + sell[i])) | 0;
        ans.push(Math.min(x, count[i]));
    }
    return ans;
}

评论