美团第二次笔试

最后一题有没有大佬教教
死磕了好久，感觉已经做的没问题了，最后还是爆零
我的思路是前缀和先算一轮最大的区间，对这个区间的所有数乘k，再重新算前缀和，对最小区间的所有数再乘k，最后累加
已经考虑到两次先后分开算了，不知道为什么还是一分没有，求大佬指点

全部评论

推荐最新楼层

ARASHI_YUKI

西安电子科技大学深度学习

k等于和小于0的时候策略会不一样吧，但是不知道为什么我也是0

1 回复分享

发布于 2024-08-17 21:15 日本

秋招失意0offer小丑勤

门头沟学院 Java

举个反例 [10,-9,10] k = 2 ; 按照你的算法，第一轮会选择 [1,3] 变成 [20,-18,20] ,第二轮选择区间[2,2], 变成[20,-36,20];sum = 4; 但最优解是第一轮[1,1] 变成[20,-9,10] 第二轮[2,2]变成[20,-18,10] sum = 12 > 4 。所以你的方法就算k > 0 这种情况下也是错的，爆0不冤

点赞回复分享

发布于 2024-08-18 09:47 浙江

收了我吧0_0

西北工业大学算法工程师

考虑了k小于等于0，也是爆零，同样是用前缀和思想做的，自测测了n个都没问题

点赞回复分享

发布于 2024-08-17 21:52 陕西

qzylalala

华中科技大学 C++

有博弈的，第一次操作会影响第二次操作。比如第一次区间内可能有负数，如果第二次求得的区间仍然包含这个负数，那么这个负数其实是 * k^2 的。所以这个思路本身就不对。

点赞回复分享

发布于 2024-08-17 21:37 上海

01-22 10:36

已编辑

牛客运营

【牛客娘创作大赏】来生成牛客娘表情包，送牛币，送牛客娘周边

活动规则：你可以使用任何AI工具，生成牛客娘表情包，发送你的生成提示词+图片至本贴评论区，并将无水印原图发送至微信群。活动奖励：1、每张 可爱的牛客娘表情包，可获得 10牛币奖励（每人上限100张） ~2、点赞量最高的前xx个评论，送牛客娘马克杯，（每25个评论，赠送一个马克杯，最多赠送20个）牛客娘表情包交流群：生成示例： 这是牛客娘的形象，帮我用牛客娘的形象画一些ACM算法竞赛相关的表情包 需要的表情包有： 摸头 （安慰） 呵呵（冷笑的呵呵） 牛魔 牛啤（左手比大拇指，右手拿着啤酒） 这次一定 比心 不许TD 要给他迎头痛击 设计要求： 1.统一使用萌系风格。 2.表情生动和肢体动作丰富、...

Xuan2333：没错没错就是我，牛客娘表情包的创作者，大家都可以自用哒awa （第5张“按住牛客娘开始思索”出自我的世界里的机械动力模组，我做这个表情包可是花了我1个多小时的时间啊qwq）最后附上所有用过的素材图，希望大家喜欢awa

wow 将图片中的人物改成两手托腮，只显示头部照片，眼睛为星星眼，表情开心，并在下方附上文字“wow” Ciallo 将第二张图的人物做出第一张图的姿势并且要在身体各处还有五官和动作完全一致，不要改背景，高分辨率，最佳质量，并在下方加上和图片相符的文字“Ciallo!” 说不出话生成这个任务面无表情，一脸犹豫，嘴角下垂，双手交叉在胸前，在中间加上一个带有一条斜杠的麦克风的表示闭麦的符号，并且在下面配上文字“说不出话” 按住牛客娘开始思索将第二张图的人物进行修改，要求是有一只手按在人物的头上，人物的眼神灵动，手略有着急的轻微摆起，头部微微抬起，并将第一张图放在第二张图的下方，高品质，把这张图的下方的黑色部分加上文字“按住牛客娘开始思索”，字体与图片里展示的“牛客娘”这三个字的字体相一致我也要WA吗将第一张图的人物的头发，脸部和衣服改成第二张图的人物的，眼睛保持不变，脸上的汗保持不变，头发的长度修改为和图片的一致，脸上不要有红晕，眼睛里不要有高光，眼睛里只要纯灰色