#技术岗笔试题求解#给定n个关卡,每个关卡要么有boss要么有商人,总共有m种宝石。玩家手里最多只能拿一块宝石。n和m在1e6量级。
boss关输入类似“b 5”,表示打完boss会掉落第5种宝石。
商人关输入类似“m 6 20”,表示商人会以20元的价格收第6种宝石。每位商人只收一种宝石。
问闯完n关后,玩家最多挣多少钱?
样例:
6 2
b 1
b 2
m 2 20
b 2
m 2 20
m 1 30
输出40,表示买卖两次2号宝石,挣40块。
全部评论
直接从后往前扫,记录一下每个宝石可以卖掉的最高价格就行了
点赞 回复 分享
发布于 2023-04-03 11:27 浙江
对于商店的位置i,找最近一个对应宝石的bossj,dp[i]=max(dp[i-1],dp[j]+a[i]),最近对应宝石boss可以通过宝石种类开索引数组二分查找
点赞 回复 分享
发布于 2023-04-01 21:53 江苏
那个岗的题啊?
点赞 回复 分享
发布于 2023-04-01 20:54 山东
思路: 首先,我们需要将输入的关卡信息进行处理,将boss关和商人关分别存储在不同的数组中。对于boss关,我们可以直接记录每个关卡掉落的宝石编号;对于商人关,我们需要记录每个商人收取的宝石编号和价格。 接下来,我们可以使用贪心算法来求解最大收益。具体地,我们可以按照宝石价格从高到低排序,然后依次尝试将每种宝石卖给商人或者留着打boss。如果当前宝石可以卖给某个商人,那么就卖给他,否则就留着打boss。这样做的正确性在于,如果我们将当前宝石留着打boss,那么后面可能会出现更高价值的宝石,而如果我们将当前宝石卖给商人,那么后面可能会出现更高价值的商人。因此,我们应该尽可能地将宝石卖给商人,以获得更高的收益。 具体实现时,我们可以使用一个指针来记录当前需要卖给商人的宝石编号,以及一个变量来记录当前已经获得的收益。对于每个关卡,我们首先判断是否是boss关,如果是,就检查当前关卡掉落的宝石是否等于指针指向的宝石编号,如果是,就将收益加上该宝石的价值,并将指针后移一位。如果不是,就继续下一个关卡。如果指针已经到达了最后一种宝石,那么剩下的所有宝石都应该留着打boss。 代码实现:
点赞 回复 分享
发布于 2023-03-31 12:35 AI生成

相关推荐

04-12 21:52
南开大学 Java
鼠鼠有点摆,去年边学着没敢投简历,没实习。从1月到现在总共面了五次,四次字节的日常(HR打电话约面试才敢去的),然后一次腾讯的暑期,都是一面挂,其他则是没给面。暑期的岗,4.2才开始海投,前面想着等字节第四次一面后再投,结果挂,而且感觉投晚了。字节投了11个,9个简历挂,剩下2个没动静。阿里全都简历挂,剩下的在"投递简历"。腾讯给了一次面。然后其他大中厂、手机厂什么的都是做完测评or笔试就没下文,打开几个看也是终止流程,感觉剩下的也应该是简历挂了。感觉是简历的原因?项目部分,几次面试,感觉面试官主要就拷问过秒杀这一个点。自己说的时候会尝试把sse那条说成亮点,但除了腾讯面试官问过一下这整个点在业务方面对用户有什么用之类的问题外,其他最多只是问一下sse八股...感觉也许不是很让面试官感兴趣。这个短链接也是无人问津,就被问过一回雪花算法的设计。也许我该拿点评改改,然后再在网上找一个什么项目,凑两个,而不是用自己现在这两个项目?或者是点评改改放前面,然后原本第一个项目,把秒杀抽掉,剩下的想办法从网上火的RAG项目里移植点亮点,或者直接就用网上的RAG项目?感觉我主要还是偏向后端开发,但是感觉如果除开点评,再拿一个项目,想不到有什么自己能掌控且跟点评不重的。然后鼠鼠之前主要的问题是担心面试让打开项目演示,然后就一直花时间在用AI整第一个项目,第二个项目都没时间整,第四次面试之前还因为太害怕被认为不熟悉项目,跟AI一起把简历的说辞做了大幅度弱化,然后暑期都是拿弱化后的简历投的,感觉是不是看上去太没有吸引力就直接给简历挂了。(图1是弱化后的,图2是弱化前的,但之前3月初投了几家好像也是简历挂。)而且因为3月花了很多时间整在跟AI整代码,导致八股和算法都没怎么看,算法之前有跟灵神题单刷一些,还算入门,但是八股只看了一些基本的,可能面试的时候只答得上来60-70%,而且表述有些混乱,都是想到哪说到哪;前面几回面试基本上都有大板块的基础八股没答出来,比如RedisZ Set数据结构,MQ延时消息、可靠性保证,JVM内存分配的过程、GC roots,JUC锁,设计模式。现在有点不知道该怎么办。求大佬们给点简历修改建议或者面试准备建议,不胜感激!
何时能不做牛马:简历每个点之间的间距可以缩一下。几乎没遇到过要演示项目的情况,即使万一遇上了你也可以说部署在其他电脑上本地没代码。nku不应该简历挂吧?抓紧背背八股练练表达,不要放弃,五六月份找到也不晚(不然还得提前入职
应届生简历当中,HR最关...
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务