$\color{Orange}{题目1：}$

题目标签

第一题应该是不太好做的如果没刷到

题目描述

某公司在招聘工程师来组建一个团队。现有 n 个工程师进行应聘，每个应聘
工程师有速度和效率两个属性。求由最多 k 个工程师组建的团队的最大表现值。团队
表现值定义为：一个团队中“所有工程师的速度和”乘以“他们中效率的最小值”。

输入样例：

n = 6, 速度 speed = [2, 10, 3, 1, 5, 8],
效率 efficiency = [5, 4, 3, 9, 7, 2], k = 2

输出样例：

60（即选择工程师 2 和工程师 5，团队表现值为 60）

原题链接

参考代码

class Solution {
public:
    using LL = long long;

    struct Staff {
        int s, e;
        bool operator < (const Staff& rhs) const {
            return s > rhs.s;
        }
    };

    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<Staff> v;
        priority_queue<Staff> q;
        for (int i = 0; i < n; ++i) {
            v.push_back({speed[i], efficiency[i]});
        }
        sort(v.begin(), v.end(), [] (const Staff& u, const Staff& v) { return u.e > v.e; });
        LL ans = 0, sum = 0;
        for (int i = 0; i < n; ++i) {
            LL minE = v[i].e;
            LL sumS = sum + v[i].s;
            ans = max(ans, sumS * minE);
            q.push(v[i]); 
            sum += v[i].s;
            if (q.size() == k) {
                sum -= q.top().s;
                q.pop();
            }
        }
        return ans % (int(1E9) + 7);
    }
};

$\color{Orange}{题目2}$

题目标签

动态规划基础题

题目描述

给定两个单词 word1 和 word2，求将 word1 转化为 word2 的最少“操作”步
数（该步数又称为两个单词的编辑距离）。这里的“操作”可以是插入一个字符、删
除一个字符、替换一个字符。

输入样例：

word1 = “horse”，word2 = “ros”

输出样例：

3（即用 r 替换 h、删除 r、删除 e）

原题链接

参考代码

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e2+ 5;
int n;
char str[2][N];
int dp[N][N];
//默写最短编辑距离
int ed(char a[], char b[])
{   
    //需要先计算字符串的长度
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=1;i<=lb;i++) dp[0][i]=i;
    for(int i=1;i<=la;i++) dp[i][0]=i;
    for(int i=1;i<=la;i++)
        for(int j=1;j<=lb;j++)
        {
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;//加1别丢
            dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]!=b[j]));
        }
    return dp[la][lb];
}
int main()
{
    cin>>str[0]+1>>str[1]+1;
    int ans=ed(str[0],str[1]);
    cout<<ans<<endl;

}

$\color{Orange}{题目3}$

题目标签

图，堆，最短路，djkstra，直接点链接可以取lc看原题

题目描述

给定由 n 个结点（下标从0开始）组成的带权
无向图，该图由一个描述边的列表组成，其中 
edges[i]= [a, b]表示连接结点 a 和 b 的一、
无向边，且该边遍历成功的概率为 succProb[i]
。给定两个结点作为起点 start 和终点 end
，找出从起点到终点成功概率最大的路径，并返
回其成功概率（若不存在从起点到终点的
路径，则返回 0）。

输入样例

n = 3, edges = [[0, 1], [1, 2], [0, 2]], 
succProb = [0.5, 0.5, 0.2], start = 0, end = 2

输出样例

0->1->2, 0.25（即从 0 到 2 有两条路径，一条为 0->2，
其成功概率为 0.2；另一条为 0->1->2，其成功概率为 0.25）

原题链接

参考代码

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<double, int>>> graph(n);
        for (int i = 0; i < edges.size(); i++) {
            auto& e = edges[i];
            graph[e[0]].emplace_back(succProb[i], e[1]);
            graph[e[1]].emplace_back(succProb[i], e[0]);
        }

        priority_queue<pair<double, int>> que;
        vector<double> prob(n, 0);

        que.emplace(1, start);
        prob[start] = 1;
        while (!que.empty()) {
            auto [pr, node] = que.top();
            que.pop();
            if (pr < prob[node]) {
                continue;
            }
            for (auto& [prNext, nodeNext] : graph[node]) {
                if (prob[nodeNext] < prob[node] * prNext) {
                    prob[nodeNext] = prob[node] * prNext;
                    que.emplace(prob[nodeNext], nodeNext);
                }
            }
        }
        return prob[end];
    }
};