2023‐08‐20 第 359 场周赛

判别首字母缩略词

• 正常模拟

class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        if (words.size() != s.size()) return false;
        
        int n = words.size();
        
        for (int i = 0; i < n; i ++) {
            string word = words[i];
            
            if (word[0] != s[i]) return false;
        }
        
        return true;
    }
};

k-avoiding数组最小总和

• 题目挺好理解的
• 就是写的时候逻辑有些问题
• 罚时两次

/*
超时
2
3
解答出错
4
5
*/

class Solution {
public:
    int minimumSum(int n, int k) {
        // 求解最小的总和
        // 除去满足和为 k 的最大数
        // 同时长度为 n
        
        unordered_map<int, int> cnt;
        vector<int> tem;
        tem.emplace_back(0);
        
        for (int i = 1; i <= n; i ++) {
            cnt[i] ++; // i 数字出现的次数
            tem.emplace_back(i);
        }
        
        // for (int i = 0; i < tem.size(); i ++) cout << tem[i] << " ";
        
        for (int i = 1; i < tem.size(); i ++) {
            if (tem[i] == 0) continue;
            
            int num = k - tem[i];
            
            if (num <= 0) break;
            
            else if (tem[i] != num && cnt[num] > 0) cnt[num]--, tem[num] = 0;
        }
        
        for (int i = 0; i < tem.size(); i ++) cout << tem[i] << " ";
        cout << endl;
        
        vector<int> res;
        
        for (int i = 0; i < tem.size(); i ++) {
            if (tem[i] > 0) res.emplace_back(tem[i]);
        }
        
        // for (int i = 0; i < res.size(); i ++) cout << res[i] << " ";
        
        
        int idx = res.size() - 1;    
        int f = res[idx] + 1; // 待添加的数字
        
        while (res.size() < n) {
            
            if (cnt[k - f] > 0) f ++; // 如果添加的数字和以前的数字有冲突
            
            else res.emplace_back(f), f ++;
        }
        
        for (int i = 0; i < res.size(); i ++) cout << res[i] << " ";
        
        return accumulate(res.begin(), res.end(), 0);
    }
};

销售利润最大化

• dp
• 没有写出来
• 参考如下

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>> &offers) {
        vector<vector<pair<int, int>>> groups(n);
        for (auto &offer: offers)
            groups[offer[1]].emplace_back(offer[0], offer[2]);

        vector<int> f(n + 1);
        for (int end = 0; end < n; end++) {
            f[end + 1] = f[end];
            for (auto &[start, gold]: groups[end])
                f[end + 1] = max(f[end + 1], f[start] + gold);
        }
        return f[n];
    }
};