第 368 场 LeetCode 周赛题解

A 元素和最小的山形三元组 I

前后缀操作：求出前后缀上的最小值数组，然后枚举 $j$

class Solution {
public:int minimumSum(vector<int> &nums) {int n = nums.size();vector<int> l(n), r(n);//l[i]=min{nums[0],...,nums[i]}, r[i]=min{nums[i],...,nums[n-1]}l[0] = nums[0];for (int i = 1; i < n; i++)l[i] = min(l[i - 1], nums[i]);r[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--)r[i] = min(r[i + 1], nums[i]);int res = INT32_MAX;for (int j = 1; j < n - 1; j++)if (l[j - 1] < nums[j] && r[j + 1] < nums[j])res = min(res, l[j - 1] + nums[j] + r[j + 1]);return res == INT32_MAX ? -1 : res;}
};

---

B 元素和最小的山形三元组 II

同 A …

class Solution {
public:int minimumSum(vector<int> &nums) {int n = nums.size();vector<int> l(n), r(n);//l[i]=min{nums[0],...,nums[i]}, r[i]=min{nums[i],...,nums[n-1]}l[0] = nums[0];for (int i = 1; i < n; i++)l[i] = min(l[i - 1], nums[i]);r[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--)r[i] = min(r[i + 1], nums[i]);int res = INT32_MAX;for (int j = 1; j < n - 1; j++)if (l[j - 1] < nums[j] && r[j + 1] < nums[j])res = min(res, l[j - 1] + nums[j] + r[j + 1]);return res == INT32_MAX ? -1 : res;}
};

---

C 合法分组的最少组数

枚举：枚举分组中有最多下标的组的下标数 $i$ ，设一个数 $val$ 在 $nums$ 的出现次数为 $ci$ ，若 $val$ 可以满足条件的被分为若干组，则有 $ci=a\times i+b\times (i-1),a\ge 0,b\ge 0$，等价于 $ci=ab\times i-b,ab\ge b\ge 0$，即 $\lceil \frac{ci}{i}\rceil \ge \lceil \frac{ci}{i}\rceil \times i-ci$

class Solution {
public:int minGroupsForValidAssignment(vector<int> &nums) {unordered_map<int, int> cnt;for (auto x: nums)cnt[x]++;unordered_map<int, int> can;int m = cnt.size();//nums中不同的数val的个数for (auto &[_, ci]: cnt) {for (int i = 1; i <= ci + 1; i++) {int ab = (ci - 1) / i + 1;int b = ab * i - ci;if (ab >= b)can[i]++;}}int mx = 1;for (auto &[gs, ci]: can)if (ci == m)//对nums中每个数val都可以划分为若干大小为gs-1和若干大小为g的组mx = max(mx, gs);int res = 0;for (auto &[_, ci]: cnt)res += (ci - 1) / mx + 1;return res;}
};

---

D 得到 K 个半回文串的最少修改次数

动态规划：首先需要预处理求出 $cost$ 数组（ $cost[i][j]$ 为将字符串 $s[i,j]$ 修改为半回文串的最少修改次数），然后设 $p[i][j]$ 为使 $s[0,i]$ 可分为 $j$ 个半回文串的最少操作数，枚举其第 $j$ 个半回文串可能的长度来进行状态转移

class Solution {
public:vector<vector<int>> cost;string s;int n;void comp_cost(int i, int j, int d) {//以d为模数(题目描述中的d)更新cost[i][j]int g = (j - i + 1) / d;//分组大小int tot = 0;for (int ind = 0; ind < d; ind++) {//枚举d个分组，若s[i,j]是半回文串则每个分组都是回文串for (int l = i + ind, r = i + ind + d * (g - 1); l <= r; l += d, r -= d)if (s[l] != s[r])tot++;}cost[i][j] = min(cost[i][j], tot);//更新cost[i][j]}int minimumChanges(string s, int k) {this->s = s;n = s.size();cost = vector<vector<int>>(n, vector<int>(n, INT32_MAX));for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {//s[i,j]int len = j - i + 1;for (int d = 1; d * d <= len; d++)if (len % d == 0) {//len的因子dcomp_cost(i, j, d);if (d != len / d && d != 1)//len的因子len/dcomp_cost(i, j, len / d);}}}int p[n][n + 1];// loc, kfor (int i = 0; i < n; i++)for (int j = 0; j <= n; j++)p[i][j] = INT32_MAX;//无效状态标志for (int i = 1; i < n; i++) {for (int j = 1; j <= (i + 1) / 2; j++) {if (j == 1)p[i][j] = cost[0][i];for (int pre = 0; i - pre > 1; pre++)if (p[pre][j - 1] != INT32_MAX)p[i][j] = min(p[i][j], p[pre][j - 1] + cost[pre + 1][i]);//考虑最后一个半回文串为s[pre+1][i]的情况}}return p[n - 1][k];}
};