排序

排序算法

常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、希尔排序、堆排序、计数排序、基数排序等。一般来说，在编程竞赛中，会直接使用库函数进行排序，并不需要自己进行实现。大多数语言的库函数排序算法为快速排序（也有一些语言为了排序的稳定性，使用了Tim排序等其他算法）。

但也有一些题目，可以结合特定的排序算法来达到排序同时求解的目的。比较经典的是利用归并排序来求逆序对数目（如Leetcode - 数组中的逆序对）。基数排序则可以应用在一些字符串处理的问题中。

此外，还有一些题目会以某种排序算法的实现为背景。

更多情况下，我们需要考虑的是如何进行排序。除了常规的升序和降序排序外，有时，我们还需要根据题目的条件和性质，考虑更为特殊的排序策略。

提示

在归并排序的过程中求解。

提示一

按照区间中点排序。

提示二

枚举分割点。前半部分的区间对应第一个解答区间；后半部分的区间对应第二个解答区间。需要预处理求出只有一个解答区间情形下的前缀最优值和后缀最优值。

提示

按照剩余能量（要求减去实际消耗）降序排列，剩余能量多的先处理，剩余能量少的后处理。