【题目来源】https://www.luogu.com.cn/problem/P1923【题目描述】输入 n 个数字 ai输出这些数字中第 k 小的数。最小的数是第 0 小。请尽量不要使用 nth_element 来写本题因为本题的重点在于练习分治算法。【输入格式】第一行有两个整数分别表示 n 和 k。第二行有 n 个整数第 i 个数表示 ai。【输出格式】一个整数表示第 k 小的数。【输入样例】5 14 3 2 1 5【输出样例】2【数据范围】对于 100% 的数据1≤ai10^91≤n5×10^6且 n 为奇数。【算法分析】● 注意本题的坑是“最小的数是第 0 小”所以针对样例所示的输出第 1 小的数时需要使用大小为k1的堆。● 数据规模 n 1e6需采用快速读入优化 I/O 性能。【算法代码】#include bits/stdc.h using namespace std; priority_queueint G; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,k,x; cinnk; while(n--) { cinx; if(G.size()k1) G.push(x); else if(xG.top()) { G.pop(); G.push(x); } } coutG.top(); return 0; } /* in: 5 1 4 3 2 1 5 out: 2 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/146336769
洛谷 P1923：求第 k 小的数 ← 对顶堆
发布时间：2026/5/30 4:16:01
【题目来源】https://www.luogu.com.cn/problem/P1923【题目描述】输入 n 个数字 ai输出这些数字中第 k 小的数。最小的数是第 0 小。请尽量不要使用 nth_element 来写本题因为本题的重点在于练习分治算法。【输入格式】第一行有两个整数分别表示 n 和 k。第二行有 n 个整数第 i 个数表示 ai。【输出格式】一个整数表示第 k 小的数。【输入样例】5 14 3 2 1 5【输出样例】2【数据范围】对于 100% 的数据1≤ai10^91≤n5×10^6且 n 为奇数。【算法分析】● 注意本题的坑是“最小的数是第 0 小”所以针对样例所示的输出第 1 小的数时需要使用大小为k1的堆。● 数据规模 n 1e6需采用快速读入优化 I/O 性能。【算法代码】#include bits/stdc.h using namespace std; priority_queueint G; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,k,x; cinnk; while(n--) { cinx; if(G.size()k1) G.push(x); else if(xG.top()) { G.pop(); G.push(x); } } coutG.top(); return 0; } /* in: 5 1 4 3 2 1 5 out: 2 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/146336769
