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

题目

分析

自己想着dp,结果比赛一直卡住。今天看y总直播又学习到了。本题直接暴力搜索就可，用四进制搜。从4^0——4^m减1，并且要排除掉每一位上3的可能。简而言之，就是将一个配料方案看成一个m位的四进制数

代码

 1 class Solution {
 2 public:
 3     int closestCost(vector<int>& a, vector<int>& b, int T) {
 4         int res = INT_MAX;
 5         int n = a.size(), m = b.size();
 6         for(int i = 0;i < n;i++){
 7             int s = a[i];  //主料
 8             for(int j = 0;j < 1<<m*2;j++){  //暴搜4^0~4^m-1
 9                 int r = s;
10                 bool flag= false;
11                 for(int k = 0;k < m;k++){ //找到不合法的
12                     int t = j >> k * 2 & 3;  //四进制扣数
13                     if(t == 3){   //每种配料选择为0、1、2，3不合法
14                         flag = true;
15                         break;
16                     }
17                     r += b[k] * t;
18                 }
19                 if(flag == true) continue;
20                 if(abs(r - T) < abs(res - T) || (abs(r-T) == abs(res - T) && r < res))
21                     res = r;
22             }
23         }
24         return res;
25     }
26 };

1. j < 1<<m*2 本操作就是四进制最大值,*2表示两位一组

2. t = j >> k * 2 & 3; //四进制扣数