用 Python 编写程序，在有界数组中查找给定索引处的最大值

pythonserver side programmingprogramming更新于 2025/12/12 21:00:17

假设我们有三个值，n、index 和 maxSum。考虑一个名为 nums 的数组，我们必须找到 nums[index] 并且 nums 满足以下条件 −

nums 的大小为 n
n 中的所有元素都是正数。
|nums[i] - nums[i+1]| <= 1 for all i, 0 <= i < n-1。
nums 所有元素的总和不超过 maxSum。
nums[index] 已最大化。

因此，如果输入为 n = 6、index = 3、maxSum = 8，则输出将为 2，因为我们可以得到一个满足所有条件的数组，如 [1,2,2,2,1,1]，并且这里 nums[3] 已最大化。

为了解决这个问题，我们将遵循以下步骤 −

left := quotient of maxSum/n, right := maxSum + 1
ans := 0
while left <右，执行
- mid := left + (right-left)/2 的商
- ind_l := (mid-1 + 1 和 (mid-index) 的最大值) * (index 和 (mid-1) 的最小值 /2 + |0 的最小值，mid-index-1| 的商
- ind_r = (mid + 1 和 (mid-(n-index-1)) 的最大值) * ((n-index) 和 mid)/2 的最小值 + |0 和 (mid-(n-index-1)-1) 的最小值| 的商
- 如果 ind_l + ind_r <= maxSum，则
  - ans := mid
  - 左:= mid+1
- 否则，
  - right := mid
返回 ans

示例

让我们看看下面的实现以便更好地理解 −

def solve(n, index, maxSum):
   left, right = maxSum//n, maxSum+1
   ans = 0
   while(left<right):
      mid = left + (right-left)//2
      ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
      ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index, mid)//2+ abs(min(0,mid-(n-index-1)-1))

      if ind_l + ind_r <=maxSum:
         ans = mid
         left = mid+1
      else:
         right = mid
   return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))