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

• Z时代
• 2024-01-10
• 分类：综合

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

• nums 的大小是 n

• n 中的所有元素都是正数。

• |nums[i] - nums[i+1]| <= 1 对于所有 i，0 <= i < n-1。

• nums 的所有元素的总和不超过 maxSum。

• nums[index] 最大化。

所以，如果输入像 n = 6, index = 3, maxSum = 8, 那么输出将是 2 因为，我们可以得到一个像 [1,2,2,2,1,1] 这样的数组，它满足所有条件，这里 nums[3] 最大化。

示例

让我们看看以下实现以获得更好的理解 -

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))

输入

6, 3, 8

2

以上是 在 Python 中的有界数组中查找给定索引处的最大值的程序 的全部内容， 来源链接： utcz.com/z/322670.html