Welcome to Subscribe On Youtube

3789. Minimum Cost to Acquire Required Items

Description

You are given five integers cost1, cost2, costBoth, need1, and need2.

There are three types of items available:

  • An item of type 1 costs cost1 and contributes 1 unit to the type 1 requirement only.
  • An item of type 2 costs cost2 and contributes 1 unit to the type 2 requirement only.
  • An item of type 3 costs costBoth and contributes 1 unit to both type 1 and type 2 requirements.

You must collect enough items so that the total contribution toward type 1 is at least need1 and the total contribution toward type 2 is at least need2.

Return an integer representing the minimum possible total cost to achieve these requirements.

 

Example 1:

Input: cost1 = 3, cost2 = 2, costBoth = 1, need1 = 3, need2 = 2

Output: 3

Explanation:

After buying three type 3 items, which cost 3 * 1 = 3, the total contribution to type 1 is 3 (>= need1 = 3) and to type 2 is 3 (>= need2 = 2).
Any other valid combination would cost more, so the minimum total cost is 3.

Example 2:

Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 2, need2 = 3

Output: 22

Explanation:

We buy need1 = 2 items of type 1 and need2 = 3 items of type 2: 2 * 5 + 3 * 4 = 10 + 12 = 22.
Any other valid combination would cost more, so the minimum total cost is 22.

Example 3:

Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 0, need2 = 0

Output: 0

Explanation:

Since no items are required (need1 = need2 = 0), we buy nothing and pay 0.

 

Constraints:

  • 1 <= cost1, cost2, costBoth <= 106
  • 0 <= need1, need2 <= 109

Solutions

Solution 1: Case Analysis

We can divide the purchasing strategy into three cases:

  1. Only buy Type 1 and Type 2 items. The total cost is $a = \textit{need1} \times \textit{cost1} + \textit{need2} \times \textit{cost2}$.
  2. Only buy Type 3 items. The total cost is $b = \textit{costBoth} \times \max(\textit{need1}, \textit{need2})$.
  3. Buy some Type 3 items, and purchase Type 1 and Type 2 items separately for the remaining needs. Let $\textit{mn} = \min(\textit{need1}, \textit{need2})$, then the total cost is $c = \textit{costBoth} \times \textit{mn} + (\textit{need1} - \textit{mn}) \times \textit{cost1} + (\textit{need2} - \textit{mn}) \times \textit{cost2}$.

Finally, we return the minimum value among the three cases, $\min(a, b, c)$.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

  • class Solution {
    public long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
        long a = (long) need1 * cost1 + (long) need2 * cost2;
        long b = (long) costBoth * Math.max(need1, need2);
        int mn = Math.min(need1, need2);
        long c = (long) costBoth * mn + (long) (need1 - mn) * cost1 + (long) (need2 - mn) * cost2;
        return Math.min(a, Math.min(b, c));
    }
}


  • class Solution {
public:
    long long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
        long long a = 1LL * need1 * cost1 + 1LL * need2 * cost2;
        long long b = 1LL * costBoth * max(need1, need2);
        int mn = min(need1, need2);
        long long c = 1LL * costBoth * mn
            + 1LL * (need1 - mn) * cost1
            + 1LL * (need2 - mn) * cost2;
        return min({a, b, c});
    }
};


  • class Solution:
    def minimumCost(
        self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int
    ) -> int:
        a = need1 * cost1 + need2 * cost2
        b = costBoth * max(need1, need2)
        mn = min(need1, need2)
        c = costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2
        return min(a, b, c)


  • func minimumCost(cost1 int, cost2 int, costBoth int, need1 int, need2 int) int64 {
	a := int64(need1)*int64(cost1) + int64(need2)*int64(cost2)
	b := int64(costBoth) * int64(max(need1, need2))
	mn := min(need1, need2)
	c := int64(costBoth)*int64(mn) +
		int64(need1-mn)*int64(cost1) +
		int64(need2-mn)*int64(cost2)
	return min(a, min(b, c))
}


  • function minimumCost(
    cost1: number,
    cost2: number,
    costBoth: number,
    need1: number,
    need2: number,
): number {
    const a = need1 * cost1 + need2 * cost2;
    const b = costBoth * Math.max(need1, need2);
    const mn = Math.min(need1, need2);
    const c = costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2;
    return Math.min(a, b, c);
}

All Problems

All Solutions