力扣第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;
    }
};