3789. Minimum Cost to Acquire Required Items

1. Description

You can buy any number of three item types. A type 1 item costs cost1 and supplies one unit of requirement 1; a type 2 item costs cost2 and supplies one unit of requirement 2.
A type 3 item costs costBoth and supplies one unit of each requirement.
Return the minimum total cost to obtain at least need1 units of requirement 1 and at least need2 units of requirement 2. Exceeding either requirement is allowed.

2. Example

Example 1

Input: cost1 = 3, cost2 = 2, costBoth = 1, need1 = 3, need2 = 2
Output: 3
Explanation: Three type 3 items supply three units of each requirement and cost 3.

Example 2

Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 2, need2 = 3
Output: 22
Explanation: Buy two type 1 items and three type 2 items for 2 * 5 + 3 * 4 = 22.

Example 3

Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 0, need2 = 0
Output: 0
Explanation: Both requirements are zero, so no purchase is needed.

3. Constraints

• 1 <= cost1, cost2, costBoth <= 10$^6$
• 0 <= need1, need2 <= 10$^9$

4. Solutions

greedy

Time complexity: O(1)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    long long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
        int common = min(need1, need2);
        long long sum = min(1LL * cost1 * common + 1LL * cost2 * common, 1LL * costBoth * common);

        int need = max(need1, need2) - common;
        int cost = need1 >= need2 ? cost1 : cost2;

        sum += 1LL * need * min(cost, costBoth);

        return sum;
    }
};