| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
Medium |
1701 |
Weekly Contest 230 Q2 |
|
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
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 ansclass 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;
}
};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;
};