2025-08-24：吃披薩。用go語言，給出一個長度爲 n 的整數數組 pizzas，pizzas[i] 表示第 i 個披薩的

2025-08-24：吃披薩。用go語言，給出一個長度爲 n 的整數數組 pizzas，pizzas[i] 表示第 i 個披薩的重量。每一天必須恰好取出 4 個披薩來食用，並把這 4 個披薩按重量從小到大排成 a ≤ b ≤ c ≤ d：

• 若是第 1、3、5… 天（奇數天），當天的體重增加值爲 d（這四個中最重的那塊）。

• 若是第 2、4、6… 天（偶數天），當天的體重增加值爲 c（這四個中第二重的）。要求將所有披薩分成 n/4 組四個爲一組（每個披薩只能用一次），並確定各組的食用順序，使得累計的體重增加值最大化。已知 n 爲 4 的倍數。求這個最大可能的總增加量。

4 <= n == pizzas.length <= 2 * 100000。

1 <= pizzas[i] <= 100000。

n 是 4 的倍數。

輸入： pizzas = [1,2,3,4,5,6,7,8]。

輸出： 14。

解釋：

第 1 天，你吃掉下標爲 [1, 2, 4, 7] = [2, 3, 5, 8] 的披薩。你增加的重量爲 8。

第 2 天，你吃掉下標爲 [0, 3, 5, 6] = [1, 4, 6, 7] 的披薩。你增加的重量爲 6。

吃掉所有披薩後，你增加的總重量爲 8 + 6 = 14。

題目來自力扣3457。

解決思路

1.排序披薩：首先將披薩按重量從大到小排序。這樣我們可以優先考慮重量大的披薩，因爲它們可能貢獻更多的增加值。

2.分組策略：總共有days = n/4天（即組數）。爲了最大化總增加量，我們需要讓奇數天分配到儘可能大的最大值（d），偶數天分配到儘可能大的次大值（c）。

3.奇數天和偶數天的分配：

• 奇數天（第1、3、5…天）直接取最大的那些值作爲d（即每組最大值）。因爲奇數天直接取最大值，所以我們可以直接取排序後最大的前odd = (days+1)/2個披薩（這些將作爲奇數天的最大值）。

• 偶數天（第2、4、6…天）需要取次大值（c）。但次大值不能直接取最大的那些（因爲最大值已經被奇數天佔用了），而是需要從剩餘的披薩中挑選較大的次大值。

4.具體分配方法：

• 排序後，最大的前odd個披薩（即排序後的前odd個）被分配給奇數天作爲最大值（d）。

• 對於偶數天，我們需要爲每組分配一個次大值（c）。這些次大值應該儘可能大，但必須避免與奇數天衝突（即不能重複使用披薩）。

• 實際上，我們可以通過間隔選取的方式：從排序後的數組中，在跳過前odd個之後，每隔一個取一個披薩（即取索引爲odd+1,odd+3,odd+5... 的披薩），共取days/2個。這些被選取的披薩將作爲偶數天的次大值（c）。

5.爲什麼這樣分配？：

• 奇數天直接取最大的前odd個披薩，這顯然是最優的（因爲奇數天直接取最大值，所以最大的幾個必須分配給奇數天）。

• 對於偶數天，我們需要次大值（c）儘可能大。但每組由4個披薩組成，最大值（d）已經很大（通常比c大），所以c不能太大（否則會浪費成爲d的機會）。實際上，我們希望c儘可能大，但又不能佔用那些可能成爲更大d的披薩（即前odd個）。

• 排序後，數組從大到小排列。前odd個已經被用作奇數天的d。接下來，我們考慮剩餘披薩中較大的那些作爲偶數天的c。但如果我們直接取剩餘最大的（即索引odd處的披薩），那麼它可能應該作爲某個組的d（但奇數天已經用完d名額），所以它只能作爲c？但注意：實際上，每個組需要4個披薩，而且d和c來自同一組。

• 更深入的解釋：爲了最大化總增加量，我們應該讓奇數天的d儘可能大（所以取前odd個最大的），然後讓偶數天的c儘可能大（但不能影響奇數天的d）。實際上，偶數天的c應該從排序後的數組中“間隔”選取：因爲如果我們取索引odd（即第odd+1大的披薩）作爲某個偶數天的c，那麼它所在的組必須有一個比它更大的d（但這個d已經被奇數天佔用了，所以這個組不能是偶數天？）。實際上，我們需要爲偶數天構造組，使得c儘可能大，同時d更大（但d已經被奇數天佔用了，所以偶數天的d必須比c大，但可能小於奇數天的d）。

• 實際上，算法中偶數天取的c是排序後數組中的索引爲odd+1,odd+3,odd+5... 的元素。這樣做的原因是：這些位置的值足夠大（因爲數組已排序），而且通過間隔選取，可以確保每個偶數天組有一個更大的d（這個d來自前odd箇中的某個，但前odd個已經分配給奇數天了？）——這裡需要更仔細的構造。

• 實際上，分組是隱含的：我們並不顯式構造每組4個披薩，而是直接計算總和。因爲問題只要求總和最大化，並不需要輸出分組方案。所以算法直接選取了貢獻值（奇數天的d和偶數天的c）並求和。

1. 排序披薩：從大到小排序後得到 [8,7,6,5,4,3,2,1]。

2. 計算天數：days = 8/4 = 2。

• 奇數天個數：odd = (2+1)/2 = 1（即第1天是奇數天）。

• 偶數天個數：days/2 = 1（即第2天是偶數天）。

3. 選取奇數天的d：取前odd=1個最大的披薩，即8。

4. 選取偶數天的c：從索引odd=1開始（即跳過前1個），每隔一個取一個，共取days/2=1個：

• 起始索引：odd=1（即第2個元素，值爲7）。

• 但算法中取的是odd + i*2 + 1？實際上，代碼中循環是for i in range(days/2)，取索引爲odd + i*2 + 1。

• 對於i=0：索引 = 1 + 0*2 + 1 = 2（即第3個元素，值爲6）。

• 所以取的是6（而不是7）。

5. 總增加量 = 8 + 6 = 14。

爲什麼取索引2（值爲6）而不是索引1（值爲7）？

• 因爲如果取索引1（7）作爲偶數天的c，那麼它所在的組需要有一個比7更大的d（至少爲8）。但最大的d（8）已經被奇數天佔用了，所以這個組不能是偶數天？實際上，我們需要避免衝突。

• 更一般地，這種間隔選取方式確保了每個偶數天的c對應的組有一個更大的d（這個d來自前odd個），並且不會重複使用披薩。

• 算法通過排序和貪心策略，直接選取貢獻值（奇數天的最大值和偶數天的次大值）求和，得到最大總增加量。

• 時間複雜度：排序時間複雜度爲 O(n log n)，後續的遍歷爲 O(n)，因此總時間複雜度爲 O(n log n)。

• 空間複雜度：排序可能使用 O(log n) 的額外空間（如快速排序的遞歸棧），因此總額外空間複雜度爲 O(log n)。

該算法不需要顯式構造分組方案，而是通過數學推導直接計算最優和。這種方法的正確性基於貪心選擇：讓奇數天分配最大的那些值作爲d，偶數天分配儘可能大（但又不與奇數天衝突）的值作爲c。間隔選取（跳過一些值）是爲了確保分組可行（即每個組有4個披薩且不重複使用）。

Go完整代碼如下：

Python完整代碼如下：