1774. 最接近目标价格的甜点成本

发表于 分类于 阅读次数： Waline： 本文字数： 693 阅读时长 ≈ 2 分钟

考点

  • 多重背包

思路

很恶心的一道题，因为题目描述不清不楚

它想表达的意思是，冰淇淋+配料的总成本的绝对值要尽可能接近target，如果绝对值相同，取总成本更小的

比如总成本为2、6离4的绝对值距离都为2，但应该取2

理解了题意就很好写了，多重背包的裸题，直接看代码即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
 public:
  int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts,
                  int target) {
    const int inf = 0x3f3f3f3f;
    int bn = baseCosts.size(), tn = toppingCosts.size(), m = 1e5;
    // 多重背包
    bool f[100001];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 0; i < tn; ++i) {
      int v = toppingCosts[i];
      for (int c = 0; c < 2; ++c) {
        for (int j = m - v; j >= 0; --j) {
          if (f[j]) f[j + v] |= f[j];
        }
      }
    }
    // 判断答案是否更优
    // 取相对距离更小的，如果相对距离一致，取实数更小的
    auto better = [&](int x, int y) -> bool {
      int ta = abs(x - target), tb = abs(y - target);
      if (ta != tb) return ta < tb;
      return x < y;
    };
    // 遍历匹配
    int ans = inf;
    for (int i = 0; i < bn; ++i) {
      int x = baseCosts[i];
      // 如果已经 >= target, 那么自己肯定是最优的, 因为配料都大于等于1
      if (x >= target) {
        if (better(x, ans)) ans = x;
        continue;
      }
      // < target的情况下, 遍历所有可能性
      // 贪心优化
      // 如果x + j <= target的情况下, 从target向左找到的第一个就是最优的
      int gap = target - x;
      for (int j = gap; j >= 0; --j) {
        if (f[j] && better(x + j, ans)) {
          ans = x + j;
          break;
        }
      }
      // 如果x + j >= target的情况下, 从target向右找到的第一个就是最优的
      for (int j = gap + 1; j <= m; ++j) {
        if (f[j] && better(x + j, ans)) {
          ans = x + j;
          break;
        }
      }
    }
    return ans;
  }
};

由于多重背包是可达性，可以用位运算滚掉它：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
 public:
  int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts,
                  int target) {
    const int inf = 0x3f3f3f3f;
    int bn = baseCosts.size(), tn = toppingCosts.size(), m = 1e5;
    // 多重背包
    bitset<100001> f;
    f[0] = 1;
    for (int i = 0; i < tn; ++i) {
      int v = toppingCosts[i];
      for (int c = 0; c < 2; ++c) f |= f << v;
    }
    // 判断答案是否更优
    // 取相对距离更小的，如果相对距离一致，取实数更小的
    auto better = [&](int x, int y) -> bool {
      int ta = abs(x - target), tb = abs(y - target);
      if (ta != tb) return ta < tb;
      return x < y;
    };
    // 遍历匹配
    int ans = inf;
    for (int i = 0; i < bn; ++i) {
      int x = baseCosts[i];
      // 如果已经 >= target, 那么自己肯定是最优的, 因为配料都大于等于1
      if (x >= target) {
        if (better(x, ans)) ans = x;
        continue;
      }
      // < target的情况下, 遍历所有可能性
      // 贪心优化
      // 如果x + j <= target的情况下, 从target向左找到的第一个就是最优的
      int gap = target - x;
      for (int j = gap; j >= 0; --j) {
        if (f[j]) {
          int tot = x + j;
          if (better(tot, ans)) {
            ans = tot;
            break;
          }
        }
      }
      // 如果x + j >= target的情况下, 从target向右找到的第一个就是最优的
      for (int j = gap + 1; j <= m; ++j) {
        if (f[j]) {
          int tot = x + j;
          if (better(tot, ans)) {
            ans = tot;
            break;
          }
        }
      }
    }
    return ans;
  }
};