2144 打折購(gòu)買糖果的最小開銷
對(duì)讀者的要求
了解庫(kù)函數(shù)，排序的逆序函數(shù)寫法
理解步長(zhǎng)/取模運(yùn)算的概念
貪心思維：以最小代價(jià)博取最大利益
方法一：排序 + 枚舉
對(duì)數(shù)組元素按照數(shù)值逆序排序，通過設(shè)置步長(zhǎng)取出三元組，累加其中最大的和較大元素。判斷邊界條件，兩者的位序均不能超過數(shù)組長(zhǎng)度。
Python版本
?
C++版本
復(fù)雜度分析
時(shí)間復(fù)雜度：O(
nlogn)。 此處的N指的是list.sort()所用排序算法TimeSort的時(shí)間復(fù)雜度nlogn。空間復(fù)雜度：O(1)。
方法二：一次遍歷 + 模運(yùn)算
書接上文，我們知道三元組中，僅有最大數(shù)和次大數(shù)字會(huì)作為代價(jià)被累加，而他們?cè)谌M中的位序分別是 [0, 1, 2] 因此可以求模運(yùn)算直接累加，對(duì)位序模3即可。
Python版本
C++版本
復(fù)雜度分析
時(shí)間復(fù)雜度：O(
nlogn)。 此處的N指的是list.sort()所用排序算法TimeSort的時(shí)間復(fù)雜度nlogn。空間復(fù)雜度：O(1)。
備注
AddressSanitizer錯(cuò)誤中的堆棧溢出，不僅可能來自于循環(huán)中的越界，可能來自于排序算法的遞歸實(shí)現(xiàn)，規(guī)則錯(cuò)誤陷入死循環(huán)則可能導(dǎo)致溢出，因此編寫正確的排序算法非常重要，考慮到本題認(rèn)可免費(fèi)額度可以與三元組中較大值相等，因此我會(huì)考慮按照大于等于的規(guī)則排序，但是該排序規(guī)則將導(dǎo)致程序報(bào)錯(cuò)，也就是上文的堆棧溢出。可以改為大于，同值將會(huì)傳遞數(shù)值之間的相對(duì)關(guān)系，而非重新局部排序；
