力扣第406场周赛

力扣第406场周赛

100352. 交换后字典序最小的字符串 - 力扣（LeetCode）

贪心，从$0$开始扫描到$n$如果有一个可以交换的就立马交换

class Solution {
public:string getSmallestString(string s) {for(int i=1;i<s.size();i++){if(s[i]%2==s[i-1]%2){if(s[i]<s[i-1]){swap(s[i],s[i-1]);break;}}}return s;}
};

思路：用$set$把$nums$中的元素全放在$set$里，遍历$list$只要$list->val$在$set$中就删除。

$tip:$要创建一个虚拟节点防止越界

class Solution {
public:ListNode* modifiedList(vector<int>& nums, ListNode* head) {set<int> st(nums.begin(), nums.end());ListNode* t = new ListNode(0);t->next = head;ListNode* p = t;while (p->next != nullptr) {if (st.count(p->next->val)) {p->next = p->next->next;} else {p = p->next;}}ListNode* res = t->next;return res;}
};

100367. 切蛋糕的最小总开销 II - 力扣（LeetCode）

$T3$和$T4$是一样的无非是$n$的范围不一样。

比赛的时候没想那么多，直接上了个贪心，没想到AC了

思路是，不管是水平的切还是垂直的切，每次都先把最大的切了，然后再切小的，这个思路是看样例一的动画图猜出来的。

具体证明步骤：

假设水平切第$i$行的价值$h_i$大于竖着切第$i$列的价值$v_i$也就是：$h_i>v_i$

每次切完以后会多出一块。如果是水平切完以后，竖着就要多切一块

例如这样水平切以后，竖着切每次都要多切一次，同理，如果竖着切了一次后，水平也要多切一次

我们记水平块数是$h{c}_i$,竖块是$v{c}_i$

我们得先水平切的后竖着切所需要的花费是：

$h{c}_i\ast h_i+(v{c}_i+1)\ast v_i=h{c}_i\ast h_i+v{c}_i\ast v_i+v_i$①

然后我们先竖着切后水平切的花费是

$v{c}_i\ast v_i+(h{c}_i+1)\ast h_i=v{c}_i\ast v_i+h{c}_i\ast h_i+h_i$②

因为$h_i>v_i$所以①<②得证

typedef pair<int,char>pii;
class Solution {
public:long long minimumCost(int m, int n, vector<int>& h, vector<int>& v) {priority_queue<pii>q;for(auto x:h)q.push({x,'h'});for(auto x:v)q.push({x,'v'});int hc=1,vc=1;long long res=0;while(q.size()){auto t=q.top();q.pop();if(t.second=='h'){res+=hc*t.first;vc++;}else{res+=vc*t.first;hc++;}}return res;}
};