給定任何自然數的陣列，例如：[2, 1, 2, 3] 。 找出陣列是否可以轉換為最大陣列(print- "YES")或者如果不能(print- "NO")
為了使其成為最大陣列--將陣列的每個元素轉換為其最大元素。在上面的例子中，它將是[3, 3, 3, 3]，但通過以下規則 -
- 增加任何一個元素。
- 一次將任何兩個元素增加1（正好是2個元素。你不能一次增加一個或兩個以上的元素）
- 這樣做多次，直到你轉換的每個元素都等于最大元素（如果可能的話，列印 "YES"，否則列印 "NO"）
示例輸入：
[2, 1, 2, 3]預期輸出: "是"
解釋：
第1步：將第一個和第二個元素遞增1 -
[3, 2, 2, 3]。第2步：將第二和第三元素增加1 -
[3, 3, 3, 3]
。誰能指出解決方案--任何鏈接、類似問題、模式或解決方案？謝謝你
編輯：
我試著用這種方法來解決它 -
- 找到最大值并將其洗掉 。
- 找到每個數字的重復對，然后再找到剩余的單個數字 。
但不能完全得到正確的結果。
uj5u.com熱心網友回復：
這實際上是一個已知的面試/編程競賽問題，但它通常被表述為 "給定一個正整數陣列，你能把它們全部減少到零，每次兩個（或k）？"
有一個簡單的解決方案：我們只需要檢查我們是否能夠以兩步為單位達到所需的總和（即檢查奇偶性），以及在所有其他數字達到最大值時，最小的數字是否能夠達到最大值。
def is_possible（nums: List[int]) -> bool:
最小的，最大的 = min(nums), max(nums)
total_needed = sum(maximum - x for x in nums)
if total_needed % 2 == 1:
return False: return
return 2 *（最大-最小）<= total_needed
這給出了：
assert is_possible([6, 6, 10] == True)
assert is_possible([2, 1, 2, 3]) == True.
assert is_possible([1, 5, 5, 9]) == True.
assert is_possible([1, 2, 9]) == False]
assert is_possible([1, 4, 9, 10]) == Falseassert is_possible([1, 6, 6, 9]) == False一個更具體的問題宣告
這個問題的一個不幸的特點是，盡管直覺上的解決方案很簡單，但這個解決方案的完整證明卻相當長。 這個問題的原始陳述在 "最大陣列 "這個短語的含義上引起了混淆，所以我將嘗試對這個問題進行精確的數學描述，然后再進行轉換。然后，這將解釋為什么代碼為該問題實施了自然的 "貪婪策略"，以及為什么該策略能夠發揮作用。
原始問題：給定一個長度為n > 1的正整數的零索引陣列A，允許你執行以下任意次數的操作。選擇兩個不同的索引i, j與0 <= i < j < n，使得A[i] < max(A)和A[j] < max(A)，并遞增A[i]和A[j]。判斷你是否能使所有的陣列元素相等。
貪婪的策略
對這個問題的 "貪婪 "或粗暴的解決方案，如果不考慮性能的話，將從 A 中選擇兩個最小的元素并遞增，重復這樣做，直到 A 中的所有元素或除一個元素外的所有元素都等于 max(A)。如果正好有一個元素不等于max(A)，我們就失敗了，這個任務是不可能的（這個說法需要證明）；否則顯然是可能的。
def is_possible_brute_force（nums。List[int]) -> bool:
largest = max(nums)
nums.sort()
while nums[0] != largest:
first = nums.pop(0)
第二 = nums.pop(0)
if second == largest and first != largest: # 如果正好有一個數字不是最大的。
return False
bisect.insort(nums, first 1)
bisect.insort(nums, second 1)
return all(x == largest for x in nums) # Always true
我們的目標是模擬這個程式的結果，而不需要實際操作。我們可以立即觀察到，如果A的元素與max(A)之間的間隙之和（我們可以稱之為total_needed）是奇數，那么這個任務就不可能完成。同樣，我們也可以在不改變答案的情況下對該問題進行如下轉換：
新問題：設M=max(A)。讓B成為A[i]-> M-A[i]轉換后的A。我們現在允許的操作是遞減B的兩個不同的索引，我們的目標是達到零陣列。我們的目標是達到零陣列。
從B和遞減的角度來考慮會更容易。你可能想到的第一個策略是：反復遞減B的兩個最大元素，即貪婪策略。這個策略被證明是最優的，只要存在就能找到一個解決方案。
讓Max_B = max(B)，讓Sum_B = sum(B)。由于我們知道，如果Sum_B是奇數，則不存在解決方案，因此我們可以假設Sum_B從這里開始是偶數。有兩種可能性：
Max_B > Sum_B - Max_B。在這種情況下，無論我們怎么做，在進行Sum_B - Max_B的遞減后，除了Max_B之外，所有的元素都是零，所以不可能有任何解決方案。Max_B <= Sum_B - Max_B。在這種情況下，解決方案總是可能的。
為了證明（2），只需證明兩件事。
i. 如果Max_B <= Sum_B - Max_B，那么在遞減了兩個最大的元素后，我們的新陣列仍然有Max_B <= Sum_B - Max_B。
ii. 唯一的配置是，當B的一個元素正好為非零時，沒有任何移動是可能的，在這種情況下，Max_B > Sum_B - Max_B
第一個宣告的證明是代數操作和案例分析，這相當不令人驚訝，所以我將從這個已經很長的證明中省略。第一個Python代碼片段現在可以理解為檢查total_need的奇偶性，以及我們是否處于上述情況(1)或(2)。
編輯：最初發布的代碼版本在最后一行有一個錯誤，與解釋和證明中的方程式相比，使用了一個錯誤的變數名和一個翻轉的不等號。歸功于用戶Breaking Not So Bad發現了這個問題，并表示感謝。
uj5u.com熱心網友回復：
這里有一個簡單的演算法，它應該是有效的。我們的想法是先增加最低的值：
找到最大值。讓我們稱它為最大值。
找到最大值。
找到最小值。讓我們稱它為min。如果 min = max，輸出 YES。
找到一個具有min值的元素，并將其遞增。
找到其他元素的最小值。讓我們稱它為min。如果min = max，輸出NO。
找到一個具有min值的元素（除前一個元素外）并將其遞增。
進入第2步。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/326061.html
標籤：