当前位置:网站首页>【acwing】786. 第k个数
【acwing】786. 第k个数
2022-07-07 07:46:00 【percation】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n,k;
int qs(int l, int r, int k){
if(l == r) return q[l];
int i = l - 1, j = r + 1, x = q[(l + r)/2];
while(i < j){
while(q[++i] < x) ;//实现左区间向右边前进,右区间向左边前进
while(q[--j] > x) ;
if(i < j) swap(q[i],q[j]);
}
int s1 = j - l + 1;//找到当时分界点在区间的位置,因区间从0开始,所以要加1
if(k <= s1)//当所要查询的数,在当前分界点的左边时,则进行左递归,否则进行右递归。
return qs(l, j, k);
return qs(j + 1,r, k - s1);
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 0; i < N; i++){
scanf("%d",&q[i]);
}
cout << qs(0,n-1,k) << endl;
return 0;
}
边栏推荐
- Gym - 102219j kitchen plates (violent or topological sequence)
- Phpcms realizes PC website access to wechat native payment
- LLVM之父Chris Lattner:為什麼我們要重建AI基礎設施軟件
- Why are social portals rarely provided in real estate o2o applications?
- 高数_第1章空间解析几何与向量代数_向量的数量积
- Embedded background - chip
- Agile course training
- There is a problem using Chinese characters in SQL. Who has encountered it? Such as value & lt; & gt;` None`
- 2020ccpc Weihai J - Steins; Game (SG function, linear basis)
- ISP、IAP、ICP、JTAG、SWD的编程特点
猜你喜欢
随机推荐
Finally, there is no need to change a line of code! Shardingsphere native driver comes out
MCU与MPU的区别
柏拉图和他的三个弟子的故事:如何寻找幸福?如何寻找理想伴侣?
Hcip first day notes sorting
学习记录——高精度加法和乘法
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
Weekly recommended short videos: what are the functions of L2 that we often use in daily life?
一大波开源小抄来袭
Introduction to energy Router: Architecture and functions for energy Internet
[original] what is the core of programmer team management?
运用tensorflow中的keras搭建卷积神经网络
为什么安装mysql时starting service报错?(操作系统-windows)
Applet sliding, clicking and switching simple UI
大整数类实现阶乘
【学习笔记-李宏毅】GAN(生成对抗网络)全系列(一)
虚数j的物理意义
字节跳动 Kitex 在森马电商场景的落地实践
Official media attention! The list of top 100 domestic digital collection platforms was released, and the industry accelerated the healthy development of compliance
C socke server, client, UDP
ORM model -- associated fields, abstract model classes