2021-01-03 16:34 湖南工业大学 C++

关注

一个简单的贪心问题

问题:

${假设你选n件物品,选这个物品的价值是a_i,不选这个物品你将失}$
${去b_i,问你选m件物品得到的价值最大是多少?}$

解决方案:

${按a_i+b_i排序,选m个最大的就好.}$

证明:

${假设你当前值为0,得到一个值你将+a_i,失去一个值你}$
${将(-b_i),那么这件物品对于你答案的影响就是a_i+b_i的.}$

${用交换的方法更好理解,假如我选现在有n件物品,物}$
${品i:a_{i},b_{i}.物品i+1:a_{i+1},b_{i+1}.假如我现在只}$
${能在这两件物品中选一件,选i而不选i+1,那么我得到}$
${的价值就是(a_i-b_{i+1}),同理另外一种选i+1而不选i}$
${得到的答案吧是(a_{i+1}-b_{i}),假设我选第一个}$
${的优先级要大于第二个的话,且当(a_i-b_{i+1})>(a_{i+1}-b_{i})时}$
${成立,移项就是(a_i+b_{i})>(a_{i+1}+b_{i+1})成立.}$

后记:

${遇到很多次了,希望都能秒了这种贪心.}$

lpt的小屋文章被收录于专栏

我想要一份甜甜的爱情

全部评论

推荐最新楼层

07-22 00:47

汤臣倍健_人力_HR

汤臣倍健面经—市场管培生

其实最难的不是offer，而是进入了公司，发现累的要死，很多同学进入了工作后，朋友圈就没有更新过了，所以大家在签约的时候一定要打听清楚！ 目前的重点还是先尽量投，尽量拿到！offer就和抢演唱会票一样，抢完第一波之后等回流了，大佬拿着再多意向书，最后也只能签一个，，越厉害的，拿的offer越多，且都是非线性增长的，只要上面的人释放完意向，紧接着链式反应，大家都会有有offer的第一轮 3个人一组 面试官问问题挨个回答1.自我介绍2.简历深挖，对市场策略的内容问的非常细，问了很多候选人是如何理解xx市场的问题3.如果让你在闲鱼卖汤臣的产品，怎么写文案4.最近印象比较深的消费品5.对汤臣倍健的品牌...

点赞评论收藏

分享

07-22 09:32

门头沟学院客户端其它

实习，你就这么偷

我接触到的实习要么是啥也不管，纯让干杂活，要不然就是上来直接上压力，主打一个钱不白花。但是这两种实习模式，都很难学到什么，一种是纯闲，散养状态，实习完可能连公司项目都不知道，另一种忙到没时间停下来思考，纯纯黑奴。在这种情况下，那怎么做才能真学到东西呢，往下看！偷，也是回到这个话题了。先偷技术思维。既然来实习来了，既然这是个公司，那么公司的项目他一定比你自己照着B站敲得烂大街的项目更强，项目的技术可能不是最新的，但是你要明白技术只是工具，你要偷的是思维，举个例子，为什么力扣上同一道算法题，有的解法又快又省空间，为什么你写的又慢又占空间，就是因为你的思维没想到那种方法，简单的增删改查，你写的很臃肿...

码农索隆：想要进步，不能光被动的接受，要主动起来，兄弟们

投递哔哩哔哩等公司10个岗位

点赞评论收藏

分享

07-04 16:47

山东理工大学营销

退伍后的迷茫

Lorn的意义：你这种岗位在中国现在要么牛马天天加班，要么关系户进去好吃好喝，8年时间，真的天翻地覆了，对于资本来说你就说一头体力更好的牛马，哎，退伍没有包分配你真的亏了。

点赞评论收藏

分享

07-23 15:15

吉林大学算法工程师

27届电子信息硕秋招备战思路和进度~

26届秋招已经开了，距离27届的秋招刚好还有一年，因此梳理了一下自己会什么和目标。 本科双非，硕士末九，本硕均为电子信息，一段实习，目前马上研二。 个人经历方向太多了导致目标也很泛，然而秋招需要很垂直的经历，因此想在接下来一年针对某一个方向强化一下。但是苦于不明确什么是好的，什么是不好的，所以借助平台分享一下自己的所思所想，也希望和大家交流一下。有类似经历或者背景的可以在评论区讨论一下~

点赞评论收藏

分享

评论

7

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 工作中哪个瞬间让你想离职 #

30457次浏览 230人参与

# 我对___祛魅了 #

1750次浏览 22人参与

# 中兴秋招 #

182173次浏览 2036人参与

# 和同事相处最忌讳的是__ #

1137次浏览 18人参与

# 机械人，你被简历秒挂的企业有哪些？ #

45433次浏览 292人参与

# 如何快速融入团队？ #

532次浏览 19人参与

# 打工人的精神状态 #

62481次浏览 1045人参与

# 职场常用语录大全 #

4817次浏览 41人参与

# 机械人，秋招第一次笔试的企业是哪家？ #

41841次浏览 335人参与

# 在职场上，你最讨厌什么样的同事 #

17343次浏览 174人参与

# 担心入职之后被发现很菜怎么办 #

142217次浏览 822人参与

# 哪些公司校招卡第一学历 #

82442次浏览 352人参与

# 职场人，说说你的烦心事 #

12420次浏览 104人参与

# 软开人，秋招你打算投哪些公司呢 #

109552次浏览 989人参与

# 秋招想进国企该如何准备 #

77287次浏览 427人参与

# 机械人晒出你的简历 #

87103次浏览 714人参与

# 工作一周年分享 #

32240次浏览 193人参与

# 金融财会交流会 #

112809次浏览 386人参与

# 如果重来一次你还会读研吗 #

180424次浏览 1809人参与

# 我的职场心眼子段位 #

36173次浏览 683人参与

# 牛油的搬砖plog #

85008次浏览 597人参与

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