杂寄
Preface
杂记不是鲜花emm
1. next_permutation 是怎么实现的
首先有一个非常不好的现象，就是大家有 STL 之后就不学某些算法了，就比如 sort 和 nth_element 。让我们来看看 next_permutation 是怎么做的。
next_permutation 的时间复杂度是 \(\mathcal O(n\log n)\) 的
算法分为以下几个步骤：
- 找到一个以序列末尾结束的最长递减区间
例如
abcdcb中的dcb
- 将该区间前一个数与区间中最后一个严格比他大的数交换位置，即不改变顺序
例如将上例中的
c与dcb中的d交换位置。此处需做二分查找。
- 将该区间翻转
要找到下一个字典序，那么就要尽可能小地改变序列，我们就找到最后一个可以变大的数，
将他变大一点点，然后把后面的重置成字典序最小的状态保证一定是下一个。
2. wqs 二分
刚刚看了一下 wqs 二分，这是一种用来解决一类恰好选 k 个的最优化问题的，且要求 \(f(x)\) 即关于选择个数的答案函数是凸函数。
此时，我们可以二分一条切线的斜率，通过取消恰好选 k 个的限制快速求解切点，然后向目标切点逼近。
标签：,二分,wqs,切点,next,permutation,区间 From： https://www.cnblogs.com/haozexu/p/18299316