分类讨论 3800, 3789

3800. Minimum Cost to Make Two Binary Strings Equal

You are given two binary strings s and t, both of length n, and three positive integers flipCost, swapCost, and crossCost.

You are allowed to apply the following operations any number of times (in any order) to the strings s and t:

• Choose any index i and flip s[i] or t[i] (change '0' to '1' or '1' to '0'). The cost of this operation is flipCost.
• Choose two distinct indices i and j, and swap either s[i] and s[j] or t[i] and t[j]. The cost of this operation is swapCost.
• Choose an index i and swap s[i] with t[i]. The cost of this operation is crossCost.

Return an integer denoting the minimum total cost needed to make the strings s and t equal.

Example 1:

Input: s = "01000", t = "10111", flipCost = 10, swapCost = 2, crossCost = 2

Output: 16

Explanation:

We can perform the following operations:

• Swap s[0] and s[1] (swapCost = 2). After this operation, s = "10000" and t = "10111".
• Cross swap s[2] and t[2] (crossCost = 2). After this operation, s = "10100" and t = "10011".
• Swap s[2] and s[3] (swapCost = 2). After this operation, s = "10010" and t = "10011".
• Flip s[4] (flipCost = 10). After this operation, s = t = "10011".

The total cost is 2 + 2 + 2 + 10 = 16.

Example 2:

Input: s = "001", t = "110", flipCost = 2, swapCost = 100, crossCost = 100

Output: 6

Explanation:

Flipping all the bits of s makes the strings equal, and the total cost is 3 * flipCost = 3 * 2 = 6.

Example 3:

Input: s = "1010", t = "1010", flipCost = 5, swapCost = 5, crossCost = 5

Output: 0

Explanation:

The strings are already equal, so no operations are required. 

Constraints:

• n == s.length == t.length
• 1 <= n <= 105​​​​​​​
• 1 <= flipCost, swapCost, crossCost <= 109
• s and t consist only of the characters '0' and '1'.

class Solution:def minimumCost(self, s: str, t: str, flipCost: int, swapCost: int, crossCost: int) -> int:# scenario1 全部用flipdiff = sum([s[i] != t[i] for i in range(len(s))])flip = diff * flipCost# scenario2 尽量用swap，然后用flips_zero = sum([s[i] != t[i] and s[i] == '0' for i in range(len(s))])t_zero = diff - s_zerosmaller, bigger = min(s_zero, t_zero), max(s_zero, t_zero)swap = smaller * swapCost + (diff - smaller * 2) * flipCost# scenario3 先用crossswap,再用swap，然后用flipcross_count = (bigger - smaller) // 2smaller += cross_countbigger -= cross_countcross = cross_count * crossCost + smaller * swapCost + (diff - smaller * 2) * flipCostreturn min(flip, swap, cross)'''
3种情况:
1. 都用flip
2. swap + flip 
3. crossswap + flip100000
001111s:01000
t:01111
diff = 5
s_0 = 1
t_0 = 410000
01111
diff = 5
s_0 = 1
t_0 = 4smaller = 1
bigger = 5
cross = (bigger - smaller) // 211000
00111'''

 

3789. Minimum Cost to Acquire Required Items

 

Solved

Medium

 

Hint

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

class Solution:def minimumCost(self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int) -> int:common = min(need1, need2)common_cost = min(common * (cost1 + cost2), common * costBoth)if common < need1:common_cost += min(cost1, costBoth) * (need1 - common)elif common < need2:common_cost += min(cost2, costBoth) * (need2 - common)return common_cost