在今天的模拟赛中，有一道题需要在(mathcal{O}(n))的复杂度内求出一个无序的序列的前(k)大值的和
然后我冥思苦想良久，还是想不到怎么做，最后只能(sort)水分了...
其实C++的模板库(algorithm)里，提供了一个非常好用的函数叫(nth\_element)
调用方式为(nth\_element(a + l, a + k, a + r + 1))，意思就是在(a)数组中的区间([l, r])之间第(k)小的值放到第(k)个位置，比这个第(k)小值小的放到它的前面。同理，比这个第(k)小值大的放到它的后面
然后就可以愉快的调用了
至于原理，可以去看看这篇解释 传送门