字节青训-游戏排名第三大的分数、补给站最优花费问题
目录
不是哥们，怎么今天没办法复制粘贴问题了
一、游戏排名第三大的分数
问题描述：
小M想要通过查看往届游戏比赛的排名来确定自己比赛的目标分数。他希望找到往届比赛中排名第三的分数，作为自己的目标。具体规则如下：
1.如果分数中有三个或以上不同的分数，返回其中第三大的分数。
2.如果不同的分数只有两个或更少，那么小M将选择最大的分数作为他的目标。
请你帮小M根据给定的分数数组计算目标分数。
测试样例
样例1:
输入: n = 3,nums = [3，2，1]输出: 1
样例2:
输入: n = 2,nums = [1，2]输出: 2
样例3:
输入: n = 4,nums = [2，2，3，1]输出: 1
解题思路：
问题理解
题目要求我们找到给定数组中第三大的唯一分数。如果数组中不同的分数少于三个，则返回最大的分数。
数据结构选择
-
std::set<int, greater<int>>: 使用std::set来存储分数，并使用greater<int>作为比较器，使得集合中的元素按降序排列。这样可以确保集合中的第一个元素是最大的，第二个元素是第二大的，依此类推。 -
std::vector<int>: 将std::set中的元素复制到std::vector中，以便于访问第三大的元素。
算法步骤
-
插入元素到集合: 遍历输入数组
nums，将每个元素插入到std::set中。由于std::set会自动去重并按降序排列，因此集合中的元素将按从大到小的顺序排列。 -
复制集合到向量: 将
std::set中的元素复制到std::vector中，以便于访问第三大的元素。 -
返回结果:
- 如果
std::vector的大小大于等于3，则返回第三大的元素（即res[2]）。 - 否则，返回最大的元素（即
res[0]）。
- 如果
最终代码：
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int solution(int n, std::vector<int> nums) {
set<int,greater<int>> num;
for(auto i : nums){
num.insert(i);
}
vector<int> res(num.begin(),num.end());
if(res.size()>=3){
return res[2];
}
else{
return res[0];
}
// write code here
return 0;
}
int main() {
std::cout << (solution(3, {3, 2, 1}) == 1) << std::endl;
std::cout << (solution(2, {1, 2}) == 2) << std::endl;
std::cout << (solution(4, {2, 2, 3, 1}) == 1) << std::endl;
return 0;
}运行结果：
二、补给站最优花费问题
问题描述：
小明需要从起点A徒步到终点B，总路程需要M天，每天需要消耗1份食物。在路程中，有N个补给站可以补充食物，不同补给站的食物价格可能不同。我们需要找到一种策略，使得小明在完成徒步的过程中花费最少的钱。
输入格式
第一行为两个正整数M、N，代表总路程M天，补给站个数N
接下来N行，每行有两个非负整数A、B代表一个补给站，表示第A天经过该补给站，每份食物的价格为B元。A是从0开始严格递增的，即起点一定有补给站，补给站是按位置顺序给出的，且同一个位置最多有个补给站。输出格式
输出一个整数，表示最少花费的金额输入样例
5 4
输出样例7
说明: 在第0天买2份食物，在第2天买3份食物，共花费7元数据范围
30%的数据，N <= M <= 109， <= A< M， <= B <= 1009
80%的数据，N <= M <= 10009， <= A< M， <= B <= 1800
100%的数据，N <= M <= 1090008， <= A< M， <= B <= 1080
解题思路：
问题理解
小明需要从起点A徒步到终点B，总路程需要M天，每天需要消耗1份食物。在路程中，有N个补给站可以补充食物，不同补给站的食物价格可能不同。我们需要找到一种策略，使得小明在完成徒步的过程中花费最少的钱。
数据结构选择
- 补给站信息：我们可以使用一个数组来存储补给站的信息，每个补给站包含两个整数：天数
A和价格B。 - 最小花费：我们可以使用一个数组
minCost来记录从第0天到第i天的最小花费。
算法步骤
- 初始化：从起点开始，初始化最小花费数组
minCost，minCost[0]为0，表示第0天的最小花费为0。 - 动态规划：
- 对于每一天
i，我们需要找到前一天的最小花费，并加上当前天的食物价格。 - 如果当前天有补给站，则更新当前天的最小花费。
- 如果没有补给站，则当前天的最小花费等于前一天的最小花费。
- 对于每一天
- 结果：最终的最小花费就是
minCost[M-1]，即第M-1天的最小花费。
最终代码：
#include <iostream>
#include <vector>
#include <limits.h>
int caculate(const std::vector<std::vector<int>>& p, int j) {
// 搜索当前的最小的价格对应的索引, j为迭代的上界
int result = 0;
int min = p[0][1];
for (int i = 0; i < j; i++) {
if (p[i][1] < min) {
min = p[i][1];
result = i;
}
}
return result;
}
int get(int cost, int m, const std::vector<std::vector<int>>& p, int d) {
// m记录剩余的路程的天数，d记录当前的数组的上界
// 递归的出口
if (d <= 0) return cost;
int j = caculate(p, d);
int minPrice = p[j][1];
cost = cost + minPrice * (m - p[j][0]);
int days = p[j][0];
return get(cost, days, p, j);
}
int solution(int m, int n, const std::vector<std::vector<int>>& p) {
/*
* 每次把路程分为两段，找到最便宜的补给站之前，和之后
* 可以通过递归的方法实现，同时使用了贪心的思想
*/
int cost = get(0, m, p, n);
// std::cout << cost << std::endl;
return cost;
}
int main() {
// Add your test cases here
std::cout << (solution(5, 4, {{0, 2}, {1, 3}, {2, 1}, {3, 2}}) == 7) << std::endl;
return 0;
}运行结果：
原文地址：https://blog.csdn.net/m0_73302939/article/details/143695112
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！