下载掌阅APP，畅读海量书库
立即打开
STL提供了一些常用函数，包含在头文件#include<algorithm>中，如下所述。
（1）min( x , y )：求两个元素的最小值。
（2）max( x , y )：求两个元素的最大值。
（3）swap( x , y )：交换两个元素。
（4）find(begin,end, x )：返回指向区间[begin,end)第1个值为 x 的元素指针。如果没找到，则返回end。
（5）count(begin,end, x )：返回指向区间[begin,end)值为 x 的元素数量，返回值为整数。
（6）reverse(begin,end)：翻转一个序列。
（7）random_shuffle(begin,end)：随机打乱一个序列。
（8）unique(begin,end)：将连续的相同元素压缩为一个元素，返回去重后的尾指针。不连续的相同元素不会被压缩，因此一般先排序后去重。
（9）fill(begin,end,val)：将区间[begin,end)的每个元素都设置为val。
（10）sort(begin,end,compare)：对一个序列排序，参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址；compare表示排序的比较函数，可省略，默认为升序。stable_sort (begin, end, compare)为稳定排序，即保持相等元素的相对顺序。
（11 ） nth_element(begin,begin+ k ,end,compare)：使区间[begin,end)第 k 小的元素处在第 k 个位置上，左边元素都小于或等于它，右边元素都大于或等于它，但并不保证其他元素有序。
（12）lower_bound(begin,end, x )/upper_bound(begin,end, x )：两个函数都是利用二分查找的方法，在有序数组中查找第1个满足条件的元素，返回指向该元素的指针。
（13）next_permutation(begin,end)/pre_permutation(begin,end)：next_permutation()是求按字典序的下一个排列的函数，可以得到全排列。pre_permutation()是求按字典序的上一个排列的函数。
下面详细讲解后5种函数。
fill(begin,end,val)将区间[begin,end)的每个元素都设置为val。与#include<cstring>中的memset不同，memset是按字节填充的。例如，int占4字节，因此memset( a ,0x3f,sizeof( a ))按字节填充相当于将0x3f3f3f3f赋值给数组 a []的每个元素。memset经常用来初始化一个int型数组为0、-1，或者最大值、最小值，也可以初始化一个bool型数组为true(1)或false(0)。
不可以用memset初始化一个int型数组为1，因为memset( a ,1,sizeof( a ))相当于将每个元素都赋值为0000 0001 0000 0001 0000 0001 0000 0001，即将0000 0001分别填充到4字节中。布尔数组可以赋值为true，是因为布尔数组中的每个元素都只占1字节。
需要注意的是，动态数组或数组作为函数参数时，不可以用sizeof( a )测量数组空间，因为这样只能测量到首地址的空间。可以用memset( a ,0x3f, n ×sizeof(int))的方法处理，或者用fill函数填充。
如果用memset( a ,0x3f,sizeof( a ))填充double类型的数组，则经常会得到一个连1都不到的小数。double类型的数组填充极值时需要用fill( a , a + n ,0x3f3f3f3f)。
尽管0x7fffffff是32-bit int的最大值，但是一般不使用该值初始化最大值，因为0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”，它会变成一个很小的负数。0x3f3f3f3f的十进制是1061109567，也就是10 9 级别的（和0x7fffffff在一个数量级），而一般情况下的数据都是小于10 9 的，所以它可以作为无穷大使用而不至于出现数据大于无穷大的情形。另一方面，由于一般的数据都不会大于10 9 ，所以当把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”）。事实上，0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了“无穷大加无穷大还是无穷大”的需求。
（1）使用默认的函数排序。
（2）自定义比较函数。sort函数默认为升序排序。如何用sort函数实现降序排序呢？自己可以编写一个比较函数来实现，接着调用含3个参数的sort(begin,end,compare)，前两个参数分别为待排序数组的首地址和尾地址，最后一个参数表示比较的类型。自定义比较函数同样适用于结构体类型，可以指定按照结构体的某个成员进行升序或降序排序。
（3）利用functional标准库。其实对于这么简单的任务（类型支持“<”“>”等比较运算符），完全没必要自己写一个类出来，引入头文件#include<functional>即可。functional提供了一些基于模板的比较函数对象。
● equal_to<Type>：等于。
● not_equal_to<Type>：不等于。
● greater<Type>：大于。
● greater_equal<Type>：大于或等于。
● less<Type>：小于。
● less_equal<Type>：小于或等于。
● 升序：sort(begin,end,less<data-type>())。
● 降序：sort(begin,end,greater<data-type>())。
当省略最后一个参数时，该函数使区间[begin,end)第 k （ k 从0开始）小的元素处在第 k 个位置上。当最后一个参数为greater<int>()时，该函数使区间[begin,end)第 k 大的元素处在第 k 个位置上。特别注意：在函数执行后会改变原序列，但不保证其他元素有序。
输出结果如下：
lower_bound()和upper_bound()都是用二分查找的方法在一个有序数组中查找第1个满足条件的元素。
● lower_bound(begin,end, x )：从数组的begin位置到end-1位置二分查找第1个大于或等于 x 的元素，找到后返回该元素的地址，不存在则返回end。通过返回的地址减去起始地址begin，得到元素在数组中的下标。
● upper_bound(begin,end, x )：从数组的begin位置到end-1位置二分查找第1个大于 x 的元素，找到后返回该元素的地址，不存在则返回end。
● lower_bound(begin,end, x ,greater<type>())：从数组的begin位置到end-1位置二分查找第1个小于或等于 x 的元素，找到后返回该元素的地址，不存在则返回end。
● upper_bound(begin,end, x ,greater<type>())：从数组的begin位置到end-1位置二分查找第1个小于 x 的元素，找到后返回该元素的地址，不存在则返回end。
next_permutation()是求按字典序排序的下一个排列的函数，可以得到全排列。pre_permutation()是求按字典序排序的上一个排列的函数。
输出：
如果改成“while(next_permutation( a , a +2));”，则输出：
只对前两个元素进行字典序排序。显然，如果改成“while(next_permutation( a , a +1));”，则只输出：
若排列本来就最大且没有后继，则在next_permutation执行后，对排列进行字典升序排序，相当于循环。
题目描述（POJ3579）： 给定 N 个数 X 1 , X 2 ,…, X N ，计算每一对数字的差：| X i - X j |，1≤ i ＜ j ≤ N 。请尽快找到差的中位数！
注意，在这个问题中，中位数被定义为第 m /2个数， m 为差的数量。
输入： 输入由几个测试用例组成。每个测试用例的第1行都为 N 。然后给出 N 个数字，表示 X 1 , X 2 ,…, X N （ X i ≤10 9 ，3≤ N ≤10 5 ）。
输出： 对于每个测试，都单行输出差的中位数。
本题数据量较大， N ≤10 5 ，如果枚举每两个数的差，然后找中位数，则时间复杂度为 O ( N 2 )， N 2 ≤10 10 ，时间限制为1秒，显然超时。可以采用二分法查找差的中位数。使用algorithm头文件中的lower_bound()函数查找第1个大于或等于 a [ i ]+val的数，统计有多少个数与 a [ i ]的差值大于或等于val，步骤如下。
（1）对序列排序。可调用algorithm头文件中的sort()。
（2）二分查找，如果差值大于或等于mid的数多于一半，则向后查找，否则向前查找。
check函数统计有多少个数的差大于或等于val。对于每一个 a [ i ]，都统计有多少个数与 a [ i ]的差大于或等于val，可以采用lower_bound( a , a + n , a [ i ]+val)找到第1个大于或等于 a [ i ]+val的数 a [ k ]（相当于 a [ k ]- a [ i ]≥val），减去首地址 a 得到该数的下标 k ， n - k 即差值大于或等于val的数的个数。 n 个数两两求差，差的序列共有 n ( n -1)/2个，该序列的一半即 m ， m = n ×( n -1)/4。
（3）输出答案ans即可。
输入样例1，包含4个数1、3、2、4，求差的中位数。
（1）排序，排序后的结果如下图所示。
（2）二分搜索。 m = n ×( n -1)/4=3； l =0， r = a [ n -1]- a [0]=3，求解如下。
● mid=( l + r )/2=1，统计有多少个数的差大于或等于1。
i =0：第1个大于或等于 a [0]+1的下标为1，有 n -1=3个数与 a [0]的差大于或等于1。
i =1：第1个大于或等于 a [1]+1的下标为2，有 n -2=2个数与 a [1]的差大于或等于1。
i =2：第1个大于或等于 a [2]+1的下标为3，有 n -3=1个数与 a [2]的差大于或等于1。
i =4：第1个大于或等于 a [3]+1的下标为 n （不存在则为 n ），有 n - n =0个数与 a [3]的差大于或等于1。
cnt=3+2+1+0=6> m （ m =3），差大于或等于1的数多于一半，说明差的中位数在后半部分，ans=mid=1； l =mid+1=2， r =3，继续求解。
● mid=( l + r )/2=2，统计有多少个数的差大于或等于2。
i =0：第1个大于或等于 a [0]+2的下标为2，有 n -2=2个数与 a [0]的差大于或等于2。
i =1：第1个大于或等于 a [1]+2的下标为3，有 n -3=1个数与 a [1]的差大于或等于2。
i =2：第1个大于或等于 a [2]+2的下标为 n （不存在则为 n ），有 n - n =0个数与 a [2]的差大于或等于2。
i =4：第1个大于或等于 a [3]+2的下标为 n （不存在则为 n ），有 n - n =0个数与 a [3]的差大于或等于2。
cnt=2+1+0+0=3不大于 m （ m =3），差大于或等于2的数少于等于一半，说明差的中位数在前半部分， r =mid-1=1，此时 l =2，不满足二分条件 l ≤ r ，循环结束。
（3）输出答案ans=1。
排序的时间复杂度为 O ( n log n )，二分搜索的时间复杂度为 O (log X max )，lower_bound()函数内部也是二分查找，时间复杂度为 O (log n )，check函数的总时间复杂度为 O ( n log n )。 X max =10 9 ，log10 9 ≈log2 30 ≈30， n ≤10 5 ， n log n ≈10 6 ，在一般情况下，10 7 以内均可通过1秒测试。
check函数也可以不调用STL，直接求解：
该check函数充分利用了 a [ i ]递增的特性，总时间复杂度为 O ( n )，速度更快，但排序的时间复杂度不变。
题目描述（POJ2388）： 约翰正在调查他的牛群以寻找产奶量最平均的奶牛。他想知道这头“中位数”奶牛的产奶量是多少：一半的奶牛产奶量与“中位数”奶牛的产奶量一样多或更多；另一半与“中位数”奶牛的产奶量一样多或更少。给定奶牛的数量 N （1≤ N <10 000， N 为奇数）及其牛奶产量（1～1 000 000），找产奶量的中位数。
输入： 第1行为整数 N ；第2～ N +1行，每行都包含一个整数，表示一头奶牛的产奶量。
输出： 单行输出产奶量的中位数。
本题很简单，可以在排序后输出中位数，或者使用nth_element函数找中位数（第 n /2小），后者速度更快。
题目描述（POJ1731）： 商店经理按货物标签的字母顺序对各种货物进行分类，将所有拥有以同一个字母开头的标签的货物都存储在同一个仓库中，并用该字母标记。经理收到并登记从商店发出的货物订单，每个订单只需要一种货物。商店经理按照预订的顺序处理请求。请计算经理访问仓库的所有可能方式，以便在一天中一个接一个地解决所有需求。
输入： 输入包含一行，其中包含所需货物的所有标签（随机排列）。对每种货物都用标签的起始字母表示，只使用英文字母表中的小字母。订单数量不超过200个。
输出： 输出将包含商店经理可以访问其仓库的所有可能的订单。对每个仓库都用英文字母表中的一个小字母表示——货物标签的起始字母。仓库的每个排序在输出文件中只在单独的行上写入一次，并且包含排序的所有行必须按字母顺序排序（请参见样例）。任何输出都不会超过2MB字节。
本题其实就是按顺序输出字符串的全排列，可以使用algorithm头文件中的next_permutation函数求解。这是一个求一个排序的下一个排列的函数，可以得到全排列。
题目描述（POJ1256）： 写程序从一组给定的字母中生成所有可能的单词。例如，给定单词“abc”，应该输出单词“abc”“acb”“bac”“bca”“cab”和“cba”。在输入的单词中，某些字母可能会出现多次。对于给定的单词，程序不应多次生成同一个单词，并且这些单词应按字母升序输出。
输入： 输入由几个单词组成。第1行包含一个数字，表示单词数。以下每行各包含一个单词。单词由a到z的大小写字母组成。大小写字母应被视为不同。每个单词的长度都小于13。
输出： 对于输入中的每个单词，输出应该包含所有可以用给定单词的字母生成的不同单词。由同一输入词生成的词应按字母升序输出。大写字母在对应的小写字母之前。
提示： 大写字母在相应的小写字母之前，所以正确的字母顺序是'A'<'a'<'B'<'b'<…<'Z'<'z'。
题解： 本题要求按正确的字母顺序输出全排列，可以使用algorithm头文件中的next_ permutation函数，需要自定义优先级。
