【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(nth_element)

简介: 该题目要求输入一个奇数个整数 $n$($1 \le n < 5000000$)和一个位置 $k$,在给定的 $n$ 个不超过 ${10}^9$ 的整数中找出第 $k$ 小的数。样例输入为 `5 1` 和 `4 3 2 1 5`,输出第 $1$ 小的数,即 `2`。解决方案使用 C++ 的 `nth_element` 函数来找到第 $k$ 小的数。

【深基9.例4】求第 k 小的数

题目描述

输入 $n$($1 \le n < 5000000$ 且 $n$ 为奇数)个数字 $a_i$($1 \le a_i < {10}^9$),输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

思路

用nth_element求第 k 小的数。

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

vector<int> v;

void read(int &x)
{
   
    char ch;
    x = 0;
    while (('0' > ch || '9' < ch))
    {
   
        ch = getchar();
    }
    while (!('0' > ch || '9' < ch))
    {
   
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main()
{
   
    int n, k;
    read(n);
    read(k);
    for (int i = 0; i < n; i++)
    {
   
        int in;
        read(in);
        v.push_back(in);
    }
    nth_element(v.begin(), v.begin() + k, v.end());
    cout << v[k] << endl;
    return 0;
}
目录
相关文章
|
缓存 JavaScript 前端开发
同步加载、异步加载、延迟加载、预加载的区别
同步加载、异步加载、延迟加载、预加载的区别
392 0
|
9月前
|
敏捷开发 监控 数据可视化
关键链项目管理:全球化与本地化的完美结合
关键链项目管理(CCPM)由以色列物理学家艾利·高德拉特提出,基于“约束理论”,通过优化资源分配、引入缓冲管理和动态调整,显著提升项目效率和成功率。本文探讨了CCPM的国际化实践现状、应用优势及未来发展趋势,特别是在欧美、亚太及新兴市场的广泛应用。CCPM在缩短项目周期、提高资源利用率、降低风险和增强团队协作方面表现出色。未来,CCPM将与数字化工具深度融合,并在全球化与本地化结合中进一步普及,成为复杂项目管理的核心方法。
|
算法 索引
【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(快速排序)
该题目要求输入一组不超过5000000个奇数个整数,并找出其中第k小的数,不使用`nth_element`函数,而是通过实现快速排序来解决。样例输入为5个数1, 4, 3, 2, 5,k=1,输出第1小的数即最小值2。代码中定义了快速排序函数`quickSort`和划分函数`partition`,并使用`read`函数读取输入。在主函数中对数组进行排序后输出第k个元素。
171 0
lxml.etree.XPathEvalError: Invalid expression
lxml.etree.XPathEvalError: Invalid expression
165 4
|
8月前
|
机器学习/深度学习 人工智能 运维
[ICDE2024]多正常模式感知的频域异常检测算法MACE
[ICDE2024]多正常模式感知的频域异常检测算法MACE
|
存储 算法 编译器
【C++ 引用 】C++深度解析:引用成员变量的初始化及其在模板编程中的应用(一)
【C++ 引用 】C++深度解析:引用成员变量的初始化及其在模板编程中的应用
1667 0
|
算法
字节跳动《算法中文手册》火了,完整版 PDF 开放下载!
字节跳动《算法中文手册》火了,完整版 PDF 开放下载!
2616 0
字节跳动《算法中文手册》火了,完整版 PDF 开放下载!
|
消息中间件 存储 负载均衡
RocketMQ 5.0 架构解析:如何基于云原生架构支撑多元化场景
RocketMQ 5.0 架构解析:如何基于云原生架构支撑多元化场景
1230 124
|
存储 数据安全/隐私保护 时序数据库
InfluxDB权限配置
InfluxDB权限配置
348 1
|
存储 SQL 关系型数据库
AnalyticDB PostgreSQL构建一站式实时数仓实践
本文介绍通过 AnalyticDB PostgreSQL 版基于实时物化视图,构建流批一体的一站式实时数仓解决方案,实现一套系统、一份数据、一次写入,即可在数仓内完成实时数据源头导入到实时分析全流程。
2585 5
AnalyticDB PostgreSQL构建一站式实时数仓实践