用自己的计算机做服务器建网站,wordpress自定义缩略图,绵阳网站制作,学网站开发要学什么绪论 虽然没有AK#xff0c;但是不知道为什么排名比以前AK了都靠前。可能是因为最后一道题有些难度#xff0c;缩小了我和大佬之间的差距。最后一个小时写最后一道题#xff0c;累死累活想了一个贪心遍历的算法#xff0c;当时是一直RE#xff0c;后来下来调了调又WA了。 …绪论 虽然没有AK但是不知道为什么排名比以前AK了都靠前。可能是因为最后一道题有些难度缩小了我和大佬之间的差距。最后一个小时写最后一道题累死累活想了一个贪心遍历的算法当时是一直RE后来下来调了调又WA了。
题目分析
A: 按奇偶性交换后的最大数字
做法就是用一个数据结构去保存奇数数字和偶数数字要求这个数据结构能够返回并弹出最大值。当时没有仔细考虑直接用了一个multiset去保存因为红黑树本身就是有序的所以每次弹出最后一个节点。但是因为把前置–写成后置–了所以还RE了一发实在不应该。现在想一下应该用一个最大堆比较合适。
class Solution {
public:int largestInteger(int num) {multisetint 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(vectorint nums, int k) {using ll long long;constexpr ll MOD 1e9 7;priority_queuell, vectorll, greaterll 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_castint(ans);}
};
最后一道题的做法在这里同样适用
functionvoid() 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(vectorint 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;mapint, int mp;for (int i 0; i idx; i) mp[flowers[i]] 1;functionvoid() 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;}
};
