滴滴笔试(求第一题实现逻辑)

魔法权杖强化 题目描述： 　有一把魔法权杖，权杖上有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)

偶，多谢，我想了好久了

2与5，3与4合并不是两次吗？

如2,3,4,5,7按上面的代码，调用helper(arr,7)。那么返回值是3，也就是需要合并3次才能使最小值>=7，而实际上是2次就行。

https://blog.csdn.net/a786150017/article/details/83004490