关注
魔法权杖强化 题目描述: 有一把魔法权杖,权杖上有n颗并排的法术石(编号为1到n)。每颗法术石具有一个能量值,权杖的法术强度等同于法术石的最小能量值。权杖可以强化,一次强化可以将两颗相邻的法术石融合为一颗,融合后的能量值为这两颗法术石能量值之和。现在有m次强化的机会,请问权杖能强化到的最大法术强度是多少? 输入 第一行包含两个正整数n,m,表示n颗法术石,m次强化机会。 第二行为n个用空格隔开的正整数v1, v2, … ,vn,vi表示编号为i的法术石具有的能量值。 数据范围:1≤m<n≤100000,1≤vi≤100000 输出 输出1个整数,表示权杖的最大的法术强度。 样例输入 6 31 7 2 2 5 9样例输出8 Hint样例说明:合并1、7得到 { 8 2 2 5 9 },合并2、2得到 { 8 4 5 9 },合并4、5得到 { 8 9 9 },法术强度等于8。 错误解法 自以为是暴力,只AC 27% n, m = list(map(int, input().split())) # 6 3
arr = list(map(int, input().split())) # [1,7,2,2,5,9]
for _ in range(m):
idx = arr.index(min(arr))
if idx == len(arr)-1 or idx > 0 and arr[idx+1] > arr[idx-1]:
arr = arr[:idx-1] + [arr[idx-1] + arr[idx]] + arr[idx+1:]
else:
arr = arr[:idx] + [arr[idx] + arr[idx+1]] + arr[idx+2:]
print(min(arr))
分析错误1 - TLE错误2 - 考虑情况比如 3 2 1 4 code合并两次:3 3 4 → 6 4 → 取4 而正确方法为:5 1 4 → 5 5 → 5 正确解法 思路 from 群里某大佬 这个题变形一下: 假设我们知道最后的能量值是p的情况下 我们要判断这个序列能否在生成最小能量值为p,并且合并次数不大于m? 解决方法 1)从左往右扫,如果碰到能量值小于p的,向右合并即可,直到能量值大于或等于p 2)然后判断合并次数是不是不大于m 然后能量值p的取值范围肯定是在数组中,只需要把数组排个序,二分 伪代码 能量值的取值范围:1到所有数相加 1)直接二分1到所有数相加,取中间p2)判断helper(p)是否大于或等于m3)如果是,可以让能量值再大一些,p继续往大的二分;如果不是,往小的二分,直到得出p 时间复杂度是o(nlogk),k是最大和n*100000 代码 只保证测试用例和思路对,不知道能不能AC # 从左往右扫,如果碰到能量值小于p的,向右合并即可,直到能量值大于或等于p
def helper(arr, target):
cnt = 0
cur = 0
for num in arr:
cur += num
if cur < target: # 需要合并
cnt += 1
else:
cur = 0
return cnt
n, m = list(map(int, input().split())) # 6 3
arr = list(map(int, input().split())) # [1,7,2,2,5,9]
left = min(arr)
right = sum(arr) + 1 # 如果不加1, mid会取不到sum(arr)
while left+1 < right:
mid = (left + right) // 2
if helper(arr, mid) <= m: # 满足要求, 可以让能量值再大一些
left = mid
else:
right = mid
print(left)
查看原帖
点赞 评论
相关推荐
07-01 15:13
门头沟学院 机械工程师 点赞 评论 收藏
分享
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
06-03 11:31
四川轻化工大学 Java 点赞 评论 收藏
分享
06-09 08:44
河北金融学院 golang 点赞 评论 收藏
分享
牛客热帖
更多
- 1... 🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端4.6W
- 2... 腾讯csig暑期一二三面1.0W
- 3... 史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)7455
- 4... 腾讯云智后台开发暑期面经5812
- 5... 秋招应该侧重准备哪个部分的内容4556
- 6... 25届毕业现在在家呆了一个多月,没工作4190
- 7... 恋爱四年没想到过自己会出轨4086
- 8... 其实主包早就找到工作了,但还是每天都刷4023
- 9... 字节实习week6:听leader吐槽当前的应届生候选人们3853
- 10... 离开软件测试才发现外面没有雨3422
正在热议
更多
# 应届生,你找到工作了吗 #
1567次浏览 23人参与
# 双非应该如何逆袭? #
172110次浏览 2878人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
38006次浏览 275人参与
# 简历当中有水分算不算造假? #
2963次浏览 30人参与
# 谈薪时HR压价该怎么应对 #
205560次浏览 3177人参与
# 实习生的蛐蛐区 #
2470次浏览 33人参与
# 春招进度记录 #
339906次浏览 3157人参与
# 三一集团提前批进度交流 #
21992次浏览 138人参与
# 百度秋招提前批进度 #
104907次浏览 1121人参与
# 毕业旅行去哪玩儿 #
7624次浏览 121人参与
# 正在春招的你,也参与了去年秋招吗? #
308454次浏览 2523人参与
# 非技术岗投递进展 #
144224次浏览 1264人参与
# 双非有机会进大厂吗 #
432808次浏览 4321人参与
# 上班到公司第一件事做什么? #
60128次浏览 517人参与
# 百度工作体验 #
229286次浏览 2008人参与
# 秋招盘点:机械人值得去的企业 #
71820次浏览 670人参与
# 材料进Fab厂真的劝退吗? #
42990次浏览 184人参与
# 如果可以,你希望哪个公司来捞你 #
96413次浏览 397人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
115903次浏览 1133人参与
# 关于春招你都做了哪些准备? #
101681次浏览 666人参与
# 工作中,努力重要还是选择重要? #
139738次浏览 1703人参与