使用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

Arnab Chakraborty

更新於：2021年5月29日

208 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習