字节青训-游戏排名第三大的分数、补给站最优耗费问题 ...

目录
一、游戏排名第三大的分数
问题描述：
问题明白
数据结构选择
算法步骤
终极代码：
运行结果：
二、补给站最优耗费问题
问题描述：
输入格式
输特别式
输入样例
输出样例
解题思绪：
问题明白
数据结构选择
算法步骤
终极代码： 
运行结果：

---

不是哥们，怎么今天没办法复制粘贴问题了
一、游戏排名第三大的分数

   问题描述：

  小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]）。
    
  
  

终极代码：

1. #include <algorithm>
2. #include <iostream>
3. #include <vector>
4. #include <set>
6. using namespace std;
8. int solution(int n, std::vector<int> nums) {
9.     set<int,greater<int>> num;
10.     for(auto i : nums){
11.         num.insert(i);
12.     }
13.     vector<int> res(num.begin(),num.end());
14.     if(res.size()>=3){
15.         return res[2];
16.     }
17.     else{
18.         return res[0];
19.     }
20.     // write code here
21.     return 0;
22. }
24. int main() {
25.     std::cout << (solution(3, {3, 2, 1}) == 1) << std::endl;
26.     std::cout << (solution(2, {1, 2}) == 2) << std::endl;
27.     std::cout << (solution(4, {2, 2, 3, 1}) == 1) << std::endl;
28.     return 0;
29. }

复制代码

运行结果：

 

二、补给站最优耗费问题

   问题描述：

  小明需要从起点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天的最小耗费。
  

终极代码： 

1. #include <iostream>
2. #include <vector>
3. #include <limits.h>
5. int caculate(const std::vector<std::vector<int>>& p, int j) {
6.     // 搜索当前的最小的价格对应的索引, j为迭代的上界
7.     int result = 0;
8.     int min = p[0][1];
10.     for (int i = 0; i < j; i++) {
11.         if (p[i][1] < min) {
12.             min = p[i][1];
13.             result = i;
14.         }
15.     }
17.     return result;
18. }
20. int get(int cost, int m, const std::vector<std::vector<int>>& p, int d) {
21.     // m记录剩余的路程的天数，d记录当前的数组的上界
22.     // 递归的出口
23.     if (d <= 0) return cost;
25.     int j = caculate(p, d);
26.     int minPrice = p[j][1];
27.     cost = cost + minPrice * (m - p[j][0]);
28.     int days = p[j][0];
29.     return get(cost, days, p, j);
30. }
32. int solution(int m, int n, const std::vector<std::vector<int>>& p) {
33.     /*
34.      * 每次把路程分为两段，找到最便宜的补给站之前，和之后
35.      * 可以通过递归的方法实现，同时使用了贪心的思想
36.      */
37.     int cost = get(0, m, p, n);
38.     // std::cout << cost << std::endl;
39.     return cost;
40. }
42. int main() {
43.     // Add your test cases here
44.     std::cout << (solution(5, 4, {{0, 2}, {1, 3}, {2, 1}, {3, 2}}) == 7) << std::endl;
45.    
46.     return 0;
47. }

复制代码

运行结果：

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。