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

devtools/2024/11/13 9:17:35/

目录

一、游戏排名第三大的分数

问题描述:

问题理解

数据结构选择

算法步骤

最终代码:

运行结果:

二、补给站最优花费问题

问题描述:

输入格式

输出格式

输入样例

输出样例

解题思路:

问题理解

数据结构选择

算法步骤

最终代码: 

运行结果:


不是哥们,怎么今天没办法复制粘贴问题了

一、游戏排名第三大的分数

问题描述:

小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 

 解题思路:

问题理解

题目要求我们找到给定数组中第三大的唯一分数。如果数组中不同的分数少于三个,则返回最大的分数。

数据结构选择

  1. std::set<int, greater<int>>: 使用 std::set 来存储分数,并使用 greater<int> 作为比较器,使得集合中的元素按降序排列。这样可以确保集合中的第一个元素是最大的,第二个元素是第二大的,依此类推。

  2. std::vector<int>: 将 std::set 中的元素复制到 std::vector 中,以便于访问第三大的元素。

算法步骤

  1. 插入元素到集合: 遍历输入数组 nums,将每个元素插入到 std::set 中。由于 std::set 会自动去重并按降序排列,因此集合中的元素将按从大到小的顺序排列。

  2. 复制集合到向量: 将 std::set 中的元素复制到 std::vector 中,以便于访问第三大的元素。

  3. 返回结果:

    • 如果 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个补给站可以补充食物,不同补给站的食物价格可能不同。我们需要找到一种策略,使得小明在完成徒步的过程中花费最少的钱。

数据结构选择

  1. 补给站信息:我们可以使用一个数组来存储补给站的信息,每个补给站包含两个整数:天数A和价格B
  2. 最小花费:我们可以使用一个数组minCost来记录从第0天到第i天的最小花费。

算法步骤

  1. 初始化:从起点开始,初始化最小花费数组minCostminCost[0]为0,表示第0天的最小花费为0。
  2. 动态规划
    • 对于每一天i,我们需要找到前一天的最小花费,并加上当前天的食物价格。
    • 如果当前天有补给站,则更新当前天的最小花费。
    • 如果没有补给站,则当前天的最小花费等于前一天的最小花费。
  3. 结果:最终的最小花费就是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;
}

运行结果:

 


http://www.ppmy.cn/devtools/133255.html

相关文章

【nlp】USAD异常检测

《异常检测——从经典算法到深度学习》18 USAD&#xff1a;多元时间序列的无监督异常检测 USAD: UnSupervised Anomaly Detection on Multivariate Time Series.pdf USAD代码 一、USAD异常检测 1. problrm formulation 该段内容主要解释了单变量和多变量时间序列&#xff0c…

《Python使用sqlite3数据库》

《Python使用sqlite3数据库》 1、连接数据库2、创建游标3、执行SQL语句4、提交更改5、查询数据6、关闭连接 Python可以使用多种数据库&#xff0c;以下是一般步骤和示例&#xff1a; 1、连接数据库 首先要安装对应的数据库驱动。如使用MySQL数据库&#xff0c;要安装pymysql库…

SQL Server 2022安装要求(硬件、软件、操作系统等)

SQL Server 2022安装要求 1、硬件要求2、软件要求3、操作系统支持4、Server Core 支持5、跨语言支持6、磁盘空间要求 1、硬件要求 以下内存和处理器要求适用于所有版本的 SQL Server&#xff1a; 组件要求存储SQL Server 要求最少 6 GB 的可用硬盘驱动器空间。 磁盘空间要求随…

网站架构知识之Ansible剧本(day022)

1.剧本模式使用方法 1.创建/server/scripts/playbook目录&#xff0c;用于存放剧本 2.将/etc/ansible/hosts主机清单文件复制到该目录下&#xff0c;cp /etc/ansible/hosts . 3.书写剧本&#xff0c;剧本后缀名需要为yml,举报人你格式如下图&#xff0c;hosts代表执行的终端…

java双向链表解析实现双向链表的创建含代码

双向链表 一.双向链表二.创建MyListCode类实现双向链表创建一.AddFirst创建&#xff08;头插法&#xff09;二.AddLast创建&#xff08;尾叉法&#xff09;三.size四.remove(指定任意节点的首位删除)五.removeAll(包含任意属性值的所有删除)六.AddIndex(给任意位置添加一个节点…

简单介绍下 Java 中的 @Validated 和 @Valid 注解的区别?

文章目录 Valid&#xff1a;专注单个对象的深度验证适用场景使用示例小结 Validated&#xff1a;聚焦接口分组的批量验证适用场景使用示例小结 主要区别总结如何选择&#xff1f;总结推荐阅读文章 在 Java 开发中&#xff0c;为了确保输入数据符合我们的要求&#xff0c;少不了…

libgdiplus在MacOS M1上问题:Unable to load shared library ‘libgdiplus‘

libgdiplus在MacOS M1上问题&#xff1a;Unable to load shared library libgdiplus 问题解决步骤1步骤2 问题 在mac上的pycharm中执行下面的代码时出现下面的错误 slide.get_thumbnail( RuntimeError: Proxy error(TypeInitializationException): The type initializer for…

IntelliJ IDEA的快捷键

IntelliJ IDEA 是一个非常强大的集成开发环境&#xff0c;它提供了大量的快捷键来加速开发者的日常工作。这里为您整理了一份 IntelliJ IDEA 的快捷键大全&#xff0c;包含了编辑、导航、重构、运行等多个方面的快捷键。请注意&#xff0c;这些快捷键是基于 Windows 版本的 Int…