緒論
雖然沒有AK，但是不知道為什么排名比以前AK了都靠前。可能是因為最后一道題有些難度，縮小了我和大佬之間的差距。最后一個小時寫最后一道題，累死累活想了一個貪心遍歷的算法，當時是一直RE，后來下來調了調又WA了。
題目分析
A: 按奇偶性交換后的最大數字
做法就是用一個數據結構去保存奇數數字和偶數數字，要求這個數據結構能夠返回并彈出最大值。當時沒有仔細考慮，直接用了一個multiset去保存，因為紅黑樹本身就是有序的，所以每次彈出最后一個節點。但是因為把前置–寫成后置–了，所以還RE了一發，實在不應該。現在想一下應該用一個最大堆比較合適。
class Solution {
public:int largestInteger(int num) {multiset<int> s0, s1;string s = to_string(num);int x;for (auto c : s) {x = c - '0';if (x & 1) s1.insert(x);else s0.insert(x);}int ans = 0, y;decltype(s1)::iterator t;for (auto c : s) {x = c - '0';if (x & 1) {t = --s1.end();y = *t;s1.erase(t);} else {t = --s0.end();y = *t;s0.erase(t);}ans = ans * 10 + y;}return ans;}
};B:向表達式添加括號后的最小結果
因為數據很小，所以沒有考慮直接模擬。雖然可以考慮預處理出每個位置的數字，但是因為實在太小了，已經懶得去考慮預處理了，直接模擬。
class Solution {
public:string minimizeResult(string expression) {int pos_p = expression.find('+');int n = expression.size();int a, b, c, d, ans = INT_MAX, x, y,t ;auto calc = [&](int l, int r) -> int {int ans = 0;for (int i = l; i < r; ++i) {ans = ans * 10 + expression[i] - '0';}return ans;};for (int i = pos_p - 1; i >= 0; --i) {for (int j = pos_p + 1; j < n; ++j) {a = calc(0, i);b = calc(i, pos_p);c = calc(pos_p + 1, j + 1);d = calc(j + 1, n);if (a == 0) a = 1;if (d == 0) d = 1;t = a * (b + c) * d;if (t < ans) {x = i;y = j + 1;ans = t;}}}string s;s.append(expression.substr(0, x));s.append("(");s.append(expression.substr(x, y - x));s.append(")");s.append(expression.substr(y, n - y));return s;}
};C:K 次增加后的最大乘積
每次可以選擇一個數字增加1，使得最后的總乘積最大。經過觀察，發現如果增加1次，那么應該增加最小的數字，因為這樣總體的和增加的最大。當時時間比較緊迫，沒有多想直接按照這個思路寫了，然后過了。
當時的做法是用一個最小堆，每次取出堆頂元素然后加一再放入堆中，這樣的復雜度是O(nlogn)，因為n不是太大，所以還可以接受。做最后一道題的時候也需要這樣一個數據結構，給集合中最小的數字增加1，增加k次，為了優化，我使用map保存每個數字出現的次數。因為map自身是有序的，所以我只需要將第一個元素增加。
class Solution {
public:int maximumProduct(vector<int>& nums, int k) {using ll = long long;constexpr ll MOD = 1e9 + 7;priority_queue<ll, vector<ll>, greater<ll>> q;for (auto x : nums) q.push(x);ll x;while (k--) {x = q.top(); q.pop();q.push(x + 1);}ll ans = 1;while (!q.empty()) {ans *= q.top();q.pop();if (ans >= MOD) ans %= MOD;}return static_cast<int>(ans);}
};最后一道題的做法在這里同樣適用
function<void()> add;
add = [&]() {if (mp.empty()) return;if (k <= 0) return;auto iter = mp.begin();int x = iter->first;int y = iter->second;if (x == target - 1) return;if (k < y) {mp[x + 1] += k;iter->second -= k;return;} else {mp.erase(iter);mp[x + 1] += y;k -= y;add();}
};這個貪心的正確性應該也不難證明：如果某次沒有增加最小值，那么，額，那么了半天也沒有想到證明。。。算了，有時間再補上吧
D:花園的最大總美麗值
沒做出來，有時間研究一下補一下，現在不想寫了。
class Solution {using ll = long long;
public:long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, ll full, ll partial) {sort(flowers.begin(), flowers.end());int n = flowers.size();int idx = n - 1, t;ll k = newFlowers;for (; idx >= 0; --idx) {t = target -flowers[idx];if (t <= 0) {} else if (t <= k) {k -= t;} else {break;}}//[0,i]ll cnt = n - idx - 1;map<int, int> mp;for (int i = 0; i <= idx; ++i) mp[flowers[i]] += 1;function<void()> add;add = [&]() {if (mp.empty()) return;if (k <= 0) return;auto iter = mp.begin();int x = iter->first;int y = iter->second;if (x == target - 1) return;if (k < y) {mp[x + 1] += k;iter->second -= k;return;} else {mp.erase(iter);mp[x + 1] += y;k -= y;add();}};add();auto getFirst = [&]() -> ll {if (mp.empty()) return 0;return mp.begin()->first;};ll ans = partial * getFirst() + cnt * full;if (idx < 0) idx = 0;for (; idx < n; ++idx) {if (flowers[idx] >= target) break;mp[flowers[idx]] += 1;k += target - flowers[idx];cnt--;add();ans = std::max(ans, partial * getFirst() + cnt * full);}return ans;}
};
函數)
