Welcome to Subscribe On Youtube
1774. Closest Dessert Cost
Description
You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:
- There must be exactly one ice cream base.
- You can add one or more types of topping or have no toppings at all.
- There are at most two of each type of topping.
You are given three inputs:
baseCosts, an integer array of lengthn, where eachbaseCosts[i]represents the price of theithice cream base flavor.toppingCosts, an integer array of lengthm, where eachtoppingCosts[i]is the price of one of theithtopping.target, an integer representing your target price for dessert.
You want to make a dessert with a total cost as close to target as possible.
Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.
Example 1:
Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10 Output: 10 Explanation: Consider the following combination (all 0-indexed): - Choose base 1: cost 7 - Take 1 of topping 0: cost 1 x 3 = 3 - Take 0 of topping 1: cost 0 x 4 = 0 Total: 7 + 3 + 0 = 10.
Example 2:
Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18 Output: 17 Explanation: Consider the following combination (all 0-indexed): - Choose base 1: cost 3 - Take 1 of topping 0: cost 1 x 4 = 4 - Take 2 of topping 1: cost 2 x 5 = 10 - Take 0 of topping 2: cost 0 x 100 = 0 Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.
Example 3:
Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9 Output: 8 Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.
Constraints:
n == baseCosts.lengthm == toppingCosts.length1 <= n, m <= 101 <= baseCosts[i], toppingCosts[i] <= 1041 <= target <= 104
Solutions
-
class Solution { private List<Integer> arr = new ArrayList<>(); private int[] ts; private int inf = 1 << 30; public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { ts = toppingCosts; dfs(0, 0); Collections.sort(arr); int d = inf, ans = inf; // 选择一种冰激淋基料 for (int x : baseCosts) { // 枚举子集和 for (int y : arr) { // 二分查找 int i = search(target - x - y); for (int j : new int[] {i, i - 1}) { if (j >= 0 && j < arr.size()) { int t = Math.abs(x + y + arr.get(j) - target); if (d > t || (d == t && ans > x + y + arr.get(j))) { d = t; ans = x + y + arr.get(j); } } } } } return ans; } private int search(int x) { int left = 0, right = arr.size(); while (left < right) { int mid = (left + right) >> 1; if (arr.get(mid) >= x) { right = mid; } else { left = mid + 1; } } return left; } private void dfs(int i, int t) { if (i >= ts.length) { arr.add(t); return; } dfs(i + 1, t); dfs(i + 1, t + ts[i]); } } -
class Solution { public: const int inf = INT_MAX; int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) { vector<int> arr; function<void(int, int)> dfs = [&](int i, int t) { if (i >= toppingCosts.size()) { arr.push_back(t); return; } dfs(i + 1, t); dfs(i + 1, t + toppingCosts[i]); }; dfs(0, 0); sort(arr.begin(), arr.end()); int d = inf, ans = inf; // 选择一种冰激淋基料 for (int x : baseCosts) { // 枚举子集和 for (int y : arr) { // 二分查找 int i = lower_bound(arr.begin(), arr.end(), target - x - y) - arr.begin(); for (int j = i - 1; j < i + 1; ++j) { if (j >= 0 && j < arr.size()) { int t = abs(x + y + arr[j] - target); if (d > t || (d == t && ans > x + y + arr[j])) { d = t; ans = x + y + arr[j]; } } } } } return ans; } }; -
class Solution: def closestCost( self, baseCosts: List[int], toppingCosts: List[int], target: int ) -> int: def dfs(i, t): if i >= len(toppingCosts): arr.append(t) return dfs(i + 1, t) dfs(i + 1, t + toppingCosts[i]) arr = [] dfs(0, 0) arr.sort() d = ans = inf # 选择一种冰激淋基料 for x in baseCosts: # 枚举子集和 for y in arr: # 二分查找 i = bisect_left(arr, target - x - y) for j in (i, i - 1): if 0 <= j < len(arr): t = abs(x + y + arr[j] - target) if d > t or (d == t and ans > x + y + arr[j]): d = t ans = x + y + arr[j] return ans -
func closestCost(baseCosts []int, toppingCosts []int, target int) int { arr := []int{} var dfs func(int, int) dfs = func(i, t int) { if i >= len(toppingCosts) { arr = append(arr, t) return } dfs(i+1, t) dfs(i+1, t+toppingCosts[i]) } dfs(0, 0) sort.Ints(arr) const inf = 1 << 30 ans, d := inf, inf // 选择一种冰激淋基料 for _, x := range baseCosts { // 枚举子集和 for _, y := range arr { // 二分查找 i := sort.SearchInts(arr, target-x-y) for j := i - 1; j < i+1; j++ { if j >= 0 && j < len(arr) { t := abs(x + y + arr[j] - target) if d > t || (d == t && ans > x+y+arr[j]) { d = t ans = x + y + arr[j] } } } } } return ans } func abs(x int) int { if x < 0 { return -x } return x } -
const closestCost = function (baseCosts, toppingCosts, target) { let closestDessertCost = -Infinity; function dfs(dessertCost, j) { const tarCurrDiff = Math.abs(target - dessertCost); const tarCloseDiff = Math.abs(target - closestDessertCost); if (tarCurrDiff < tarCloseDiff) { closestDessertCost = dessertCost; } else if (tarCurrDiff === tarCloseDiff && dessertCost < closestDessertCost) { closestDessertCost = dessertCost; } if (dessertCost > target) return; if (j === toppingCosts.length) return; for (let count = 0; count <= 2; count++) { dfs(dessertCost + count * toppingCosts[j], j + 1); } } for (let i = 0; i < baseCosts.length; i++) { dfs(baseCosts[i], 0); } return closestDessertCost; };