使用Python查找使数组相等的最小操作次数的程序

假设我们有一个值n，考虑一个具有n个元素的数组nums，其中对于所有i，arr[i] = (2*i)+1。现在，在一个操作中，我们可以选择两个索引x和y，其中0 <= x, y < n，并从nums[x]中减去1，并向nums[y]添加1。我们必须使数组的所有元素都相同。因此，如果我们有n，我们必须找到使所有nums元素都相同所需的最小操作次数。

因此，如果输入类似于n = 4，则输出将为4，因为对于n，数组为[1,3,5,7]，现在在第一次操作后，我们可以使数组类似于[2,3,5,6]，在第二次操作后，我们可以使[3,3,5,5]，然后在第三次[4,3,4,5]，最后[4,4,4,4]。所以现在所有都相等。

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

  • ans:= 0

  • 如果n等于1，则

    • 返回ans

  • q:= (n/2) -1 的商

  • j:= 1

  • 当q>=0时，执行

    • ans:= ans + (n-j)

    • q := q - 1

    • j := j + 2

  • 返回ans

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

示例

 在线演示

def solve(n):
   ans=0
   if n==1:
      return ans
   q=(n//2)-1
   j=1
   while q>=0:
      ans=ans+(n-j)
      q-=1
      j+=2
   return ans
n = 4
print(solve(n))

输入

4

输出

4

更新于：2021年5月29日

208 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告