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