2144 打折购买糖果的最小开销

对读者的要求

• 了解库函数，排序的逆序函数写法

• 理解步长/取模运算的概念

• 贪心思维：以最小代价博取最大利益

方法一：排序 + 枚举

对数组元素按照数值逆序排序，通过设置步长取出三元组，累加其中最大的和较大元素。判断边界条件，两者的位序均不能超过数组长度。

Python版本

C++版本

复杂度分析

• 时间复杂度：O(nlogn)。 此处的N指的是list.sort()所用排序算法 TimeSort的时间复杂度 nlogn。

• 空间复杂度：O(1)。

方法二：一次遍历 + 模运算

书接上文，我们知道三元组中，仅有最大数和次大数字会作为代价被累加，而他们在三元组中的位序分别是 [0, 1, 2] 因此可以求模运算直接累加，对位序模3即可。

Python版本

C++版本

复杂度分析

• 时间复杂度：O(nlogn)。 此处的N指的是list.sort()所用排序算法 TimeSort的时间复杂度 nlogn。

• 空间复杂度：O(1)。

备注

• AddressSanitizer错误中的堆栈溢出，不仅可能来自于循环中的越界，可能来自于排序算法的递归实现，规则错误陷入死循环则可能导致溢出，因此编写正确的排序算法非常重要，

• 考虑到本题认可免费额度可以与三元组中较大值相等，因此我会考虑按照大于等于的规则排序，但是该排序规则将导致程序报错，也就是上文的堆栈溢出。可以改为大于，同值将会传递数值之间的相对关系，而非重新局部排序；

• 此处可以补充C++ STL排序中的一个重要概念：strict weak ordering ， 即严格弱序。