目录
一、游戏排名第三大的分数
问题描述:
问题理解
数据结构选择
算法步骤
最终代码:
运行结果:
二、补给站最优花费问题
问题描述:
输入格式
输出格式
输入样例
输出样例
解题思路:
问题理解
数据结构选择
算法步骤
最终代码:
运行结果:
不是哥们,怎么今天没办法复制粘贴问题了
一、游戏排名第三大的分数
问题描述:
小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 herereturn 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 herestd::cout << (solution(5, 4, {{0, 2}, {1, 3}, {2, 1}, {3, 2}}) == 7) << std::endl;return 0;
}
运行结果: