Leetcode第357场周赛

https://leetcode.cn/contest/weekly-contest-357/

C 寻找不安全路径

以所有小偷点为源点，跑多源点BFS，求出每个点到最近小偷点的曼哈顿距离，记为w[i, j]

二分答案Mid，只允许走w[i, j] >= mid的点，从源店跑DFS/BFS，看是否能抵达汇点。

D 子序列最大优雅度

反悔贪心，首先将所有项目按照利润排序，先选前k大的利润。

然后考虑往后选，如果当前项目的类别已经出现过了，用它换掉前面任何一个必然是亏的，忽略。

如果当前项目的类别没出现过，考虑类别+1，优先换掉前面不是第一个出现该类别的利润最小的项目（用栈维护），这是当前这个类别数量下的最优解。

最后所有类别数量各自的解取最大值就是答案。std::sort自定义排序函数改成传引用才过，不然会一直超时。

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        std::sort(items.begin(), items.end(), [&](std::vector<int> &x, std::vector<int> &y) {
            return x[0] > y[0];
        });
        std::set<int> st;
        std::vector<int> pr;
        long long ans = 0, Ans = 0;
        for (int i = 0; i < k; i++) {
            if (!st.count(items[i][1])) st.insert(items[i][1]);
            else pr.push_back(items[i][0]);
            ans += items[i][0];
        }
        Ans = std::max(Ans, (long long)(ans + 1ll * st.size() * st.size()));
        for (int i = k; i < items.size(); i++) {
            if (st.count(items[i][1])) continue;
            if (pr.size()) {
                ans -= pr.back();
                pr.pop_back();
                ans += items[i][0];
                st.insert(items[i][1]);
                Ans = std::max(Ans, (long long)(ans + 1ll * st.size() * st.size()));
                continue;
            }
        }
        return Ans;
    }
};