復盤與一周總結

wa穿了第3題，賽時其實想到了思路：中位數(shù)貪心，從中位數(shù)開始，用左右指針找到第一個回文數(shù)，與該回文數(shù)的代價就是答案。但是沒有考慮到左右指針同時找到回文數(shù)的情況，wa了一發(fā)之后開始改。用一個vector保存代價，只要數(shù)組長度大于2就返回其中的較小值。但是沒有注意到自己的算法是左右指針同時找，可能出現(xiàn)同一個指針找到兩次回文數(shù)的情況，此時就不是左右指針分別找到一次回文數(shù)。后面改成：數(shù)組長度大于5就返回最小值才ac，賽后重寫用第一次的思路寫了一遍，很快就ac了
現(xiàn)在想想，自己能很快想到正解，但是算法實現(xiàn)的卻不是正解，而且賽時還沒發(fā)現(xiàn)，甚至以為是思路錯了，還往平均數(shù)那塊想了會。只能說，自己在算法實現(xiàn)這塊考慮得不仔細吧，下次別著急，想慢點
至于說第4題，賽時完全沒有想到中位數(shù)貪心，想到哪了呢？我在考慮數(shù)組中數(shù)的出現(xiàn)次數(shù)，出現(xiàn)次數(shù)更多的數(shù)，最后的代價是否會小于出現(xiàn)次數(shù)更小的數(shù)。甚至想到：若一個數(shù)出現(xiàn)次數(shù)超過一半，那么把所有數(shù)變?yōu)檫@個數(shù)，此時的頻率是否最大？接著就對著這個貪心結論證啊證，最后不了了之。但題目的關鍵點是：操作次數(shù)有限，那么就要考慮如何操作能盡可能少的使用操作次數(shù)，這樣就能想到中位數(shù)了

周末這幾場打下來，發(fā)現(xiàn)自己最大的問題就是：題意的理解。一是讀假題，連題目在說什么都沒搞清楚，甚至是自以為搞清楚，然后自欺欺人地想算法去了，如abc的E題，小白賽的E題。二是沒有抓住題意的重點，只要是稍有難度的題，都需要抓住關鍵點不斷地分析，如這次的第4題，小白賽的F題

問題反而是出現(xiàn)在閱讀理解上

2967. 使數(shù)組成為等數(shù)數(shù)組的最小代價（中位數(shù)貪心 回文數(shù)判斷）

2967. 使數(shù)組成為等數(shù)數(shù)組的最小代價 - 力扣（LeetCode）

根據(jù)中位數(shù)貪心，將數(shù)組排序后，從中位數(shù)開始，分別向左和向右找到第一個回文數(shù)并計算代價，數(shù)組兩個代價中較小的即可

class Solution {
public:bool f(string s){int l = 0, r = s.size() - 1;while (l < r){if (s[l] != s[r]) return false;l ++ , r -- ;}return true;}long long minimumCost(vector<int>& nums) {sort(nums.begin(), nums.end());int mid;if (nums.size() & 1) mid = nums[nums.size() / 2];else mid = (nums[nums.size() / 2] + nums[nums.size() / 2 - 1]) / 2;long long ans1 = 4e18, ans2 = 4e18;int l = mid, r = mid;while (l >= 0){if (f(to_string(l))){long long t = 0;for (int i = 0; i < nums.size(); ++ i) t += abs(nums[i] - l);ans1 = t;break;}l -- ;}while (r < 2e9){if (f(to_string(r))){long long t = 0;for (int i = 0; i < nums.size(); ++ i) t += abs(nums[i] - r);ans2 = t;break;}r ++ ;}return min(ans1, ans2);}
};

2968. 執(zhí)行操作使頻率分數(shù)最大（中位數(shù)貪心 前綴和 滑窗）

2968. 執(zhí)行操作使頻率分數(shù)最大 - 力扣（LeetCode）

要使將數(shù)組中的某些數(shù)變成同一個數(shù)的代價最小，依然是中位數(shù)貪心
同時這個序列必須是原序列的一段連續(xù)區(qū)間。比如原數(shù)組為1，2，3，4，將1，2，3變?yōu)?的代價一定比1，2，4變?yōu)?的代價小
題目要返回代價小于等于k的情況下，最長的連續(xù)區(qū)間，對于連續(xù)區(qū)間問題，自然想到滑動窗口
那么接下來要考慮的是窗口滑動時的代價變化，除了$O(n)$暴力求代價，還能使用前綴和進行預處理，$O(1)$地求代價

class Solution {
public:int maxFrequencyScore(vector<int>& nums, long long k) {sort(nums.begin(), nums.end());int n = nums.size();vector<long long> a(n + 1), s(n + 1);for (int i = 0; i < n; ++ i) a[i + 1] = nums[i], s[i + 1] = s[i] + a[i + 1];auto f = [&](int l, int mid, int r) -> long long{long long left = (mid - l) * a[mid] - (s[mid - 1] - s[l - 1]);long long right = (s[r] - s[mid - 1]) - (r - mid + 1) * a[mid];return left + right;};int l = 1, r = 1;int ans = 0;while (r <= n){while (f(l, (l + r) / 2, r) > k) l ++ ;ans = max(ans, r - l + 1);r ++ ;}return ans;}
};