算法菜鸡备战3月2日传智杯省赛----0221

2209. 用地毯覆盖后的最少白色砖块 - 力扣（LeetCode）

力扣每日一题

class Solution {
public:// 白色最少 == 黑色最多int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {int n = floor.size();// 记忆化搜索vector memo(n + 1, vector<int>(numCarpets + 1, -1));auto dfs = [&](this auto&& dfs, int x, int y) {// 有y块地毯和x块砖，求对应的黑色最大值if (x <= y * carpetLen) {// 铺满了return x;}if (memo[x - 1][y] != -1) {// 记忆化搜索return memo[x - 1][y];}int& res = memo[x - 1][y];if (floor[x - 1] == '0') {// 遇到黑色return res = 1 + dfs( x - 1, y);}return res = max((y > 0 ? dfs( x - carpetLen, y - 1) + carpetLen : 0),dfs( x - 1, y));};return n - dfs( n, numCarpets);}
};

2

2560. 打家劫舍 IV - 力扣（LeetCode）

class Solution {
public:int minCapability(vector<int>& nums, int k) {int left = 0, right = *max_element(nums.begin(), nums.end()),n = nums.size();auto check = [&](int mid) {int tmp = 0;for (int i = 0; i < n; i++) {if (nums[i] <= mid) {i++;tmp++;if (tmp >= k) {return true;}}}cout << tmp << endl;return false;};while (left <= right) {// cout << left << ' ' << right << endl;int mid = (left + right) >> 1;if (check(mid)) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

3

778. 水位上升的泳池中游泳 - 力扣（LeetCode）

class Solution {
public:int m[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int swimInWater(vector<vector<int>>& grid) {int n = grid.size();if(n == 1){return grid[0][0];}int left = grid[0][0], right = 2500;auto bfs = [&](int mid) {queue<pair<int, int>> q;vector t(n, vector<bool>(n, false));q.push({0, 0});int qx, qy, x, y;while (q.size()) {auto [qx, qy] = q.front();q.pop();for (int i = 0; i < 4; i++) {x = qx + m[i][0], y = qy + m[i][1];if (x < 0 || x >= n || y < 0 || y >= n || t[x][y])continue;if (grid[x][y] > mid)continue;if (x == n - 1 && y == n - 1)return true;t[x][y] = true;q.push({x, y});}}return false;};while (left <= right) {int mid = (left + right) >> 1;if (bfs(mid)) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

4

2616. 最小化数对的最大差值 - 力扣（LeetCode）

class Solution {
public:int minimizeMax(vector<int>& nums, int p) {if(p == 0) return 0;ranges::sort(nums);int n = nums.size();vector<int> tmp(n - 1);for(int i = 1;i <n;i++){tmp[i - 1] = nums[i] - nums[i - 1];}n--;int left = 0,right = *max_element(nums.begin(),nums.end());auto check = [&](int mid){int a = 0;for(int i = 0;i < n;i++){if(tmp[i] <= mid){i++;a++;if(a >= p){return true;}}}return false;};while(left <= right){int mid = (left + right) >> 1;if(check(mid)){right = mid - 1;}else{left = mid + 1;}}return left;}
};