Greedy¶

Median¶

中位數貪心¶

• 中位數貪心及其證明

• 簡單證明 - 剝洋蔥法

• problem:

Median alignment (中位數對齊問題)¶

• problem:

  • Minimum Adjacent Swaps for K Consecutive Ones

  • D. A and B

思想/小結論¶

替換/取代 操作¶

• 貢獻法

  對於取代或是替換操作，可以有兩種選擇:

  1. 不操作: 此時的貢獻是原本的 \(g\)

  2. 操作: 此時的貢獻是減去原本的 \(g\) ，加上操作後產生的貢獻 \(g'\)

  \[cost = max(g, g' - g)\]

  • Leetcode #2321. 拼接数组的最大分数

    可以知道最後的答案會是 $\(\sum_i{nums1[i]} + (nums2[left] + ... +nums2[right]) - (nums1[right] + ... +nums1[right])\)$

    因此核心思想是找最大子數組 \(diff[i] = nums2[i] - nums2[i]\) 的和:

    \[\sum_i{nums1[i]} + diff[left] + ... + diff[right]\]

    對於 \(nums2\) 同理。