关注
魔法权杖强化 题目描述: 有一把魔法权杖,权杖上有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)
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
06-16 18:15
湖南人文科技学院 Java 湫湫湫不会java:1.在校经历全删了2.。这些荣誉其实也没啥用只能说,要的是好的开发者不是好好学生3.项目五六点就行了,一个亮点一俩行,xxx技术解决,xxx问题带来xxx提升。第一页学历不行,然后啥有价值的信息也没有,到第二页看到项目了,第一个项目九点,第二个项目像凑数的俩点。总体给人又臭又长,一起加油吧兄弟
点赞 评论 收藏
分享
07-03 16:55
门头沟学院 硬件开发 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 秋招什么时候开投比较合适? #
23717次浏览 318人参与
# 百度工作体验 #
223407次浏览 1972人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
27964次浏览 216人参与
# 机械人与华为的爱恨情仇 #
117159次浏览 946人参与
# 发工资后,你做的第一件事是什么 #
68161次浏览 229人参与
# 机械人集合!你是什么工程师? #
15814次浏览 89人参与
# 你觉得实习能学到东西吗 #
36319次浏览 712人参与
# 找不到好工作选择GAP真的丢人吗 #
78275次浏览 938人参与
# 我想去国央企的原因 #
59996次浏览 393人参与
# 如何准备秋招 #
20678次浏览 390人参与
# 工作中哪个瞬间让你想离职 #
25915次浏览 177人参与
# 入职第四天,心情怎么样 #
29451次浏览 417人参与
# 拼多多工作体验 #
28545次浏览 197人参与
# 多益网络求职进展汇总 #
29231次浏览 134人参与
# 快手求职进展汇总 #
547105次浏览 6001人参与
# 硬件应届生薪资是否普遍偏低? #
74086次浏览 514人参与
# 不考虑转正,实习多久合适 #
32328次浏览 145人参与
# 面试中,你被问过哪些奇葩问题? #
68560次浏览 796人参与
# 你们公司几号发工资 #
21234次浏览 140人参与
# 如果再来一次,你还会学硬件吗 #
125789次浏览 1402人参与
# 实习,不懂就问 #
46390次浏览 693人参与