【LeetCode】5690. 最接近目标价格的甜点成本

发表于 更新于 分类于 Valine：
本文字数： 399 阅读时长 ≈ 1 分钟

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

思路

  1. 位运算
  2. 二进制状态压缩
  3. 暴力枚举
1
2
3
4
101010      101010      101010
011100 &    011100 |	011100 ^
--------------------------------
001000      111110      110110
第一步：

枚举baseCosts[i]，表示选定一种基料

第二步：

每种类型的配料最多两份。

压缩至二进制状态1<<m，压缩至四进制状态1<<m *2
$4^m=2^{m*2}$
以四进制来储存所有配料选择的状态，如有两种配料

配料种类 状态 二进制状态 十进制状态
配料1 0 份 00 0
配料1 1 份 01 1
配料1 2 份 10 2
配料1 3 份(无效状态) 11 3
配料2 0 份 00 0
配料2 1 份 01 1
配料2 2 份 10 2
配料2 3 份(无效状态) 11 3

int t = j >> k * 2 & 3;
如 001100 判断第$k$种配料是否是无效状态，一种配料占两个位置，做位运算&3，因为bin(3)=0xb11

无效状态直接跳过，继续枚举

1
2
3
4
5
6
if (t == 3) {
    flag = true;
    break;
}
......
if (flag) continue;
第三步：

判断最接近target的甜点成本res

  1. r对target的绝对值比res小
  2. 绝对值相同，但是r的值更小

拓展

  1. 位运算

代码

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
class Solution {
public:
    int closestCost(vector<int>& a, vector<int>& b, int T) {
        int res = INT_MAX;
        int n = a.size(), m = b.size();
        for (int i = 0; i < n; i ++ ) {
            int s = a[i];
            for (int j = 0; j < 1 << m * 2; j ++ ) {
                int r = s;
                bool flag = false;
                for (int k = 0; k < m; k ++ ) {
                    int t = j >> k * 2 & 3;
                    if (t == 3) {
                        flag = true;
                        break;
                    }
                    r += b[k] * t;
                }
                if (flag) continue;
                if (abs(r - T) < abs(res - T) || abs(r - T) == abs(res - T) && r < res)
                    res = r;
            }
        }
        return res;
    }
};