zhangchenyi_10_old @ 2025-01-01 09:28:26
#include <bits/stdc++.h>
using namespace std;
void read(int &x){
int s=0,w=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
w=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
s=s*10+c-'0';
c=getchar();
}
x=s*w;
return;
}
int ans,n,m,a[5000010],k,t;
void f(int l,int r){
if(l==r&&l==k){
ans=a[k];
printf("%d",ans);
exit(0);
}
if(l<r){
int i=l,j=r,p=a[l];
while(i<j){
while(i<j&&a[j]>p){
j--;
}
if(i<j){
swap(a[i],a[j]);
}
while(i<j&&a[j]<=p){
i++;
}
if(i<j){
swap(a[i],a[j]);
}
}
a[i]=p;
if(i==k){
ans=a[k];
printf("%d",ans);
exit(0);
}
if(i>k){
f(l,i-1);
}
else{
f(i+1,r);
}
}
}
int main(){
read(n);
read(m);
k=1;
for(int i=1;i<=n;i++){
read(a[i]);
}
f(1,n);
printf("%d",ans);
return 0;
}
关注
by xingtiankai2023 @ 2025-01-01 10:21:45
@zhangchenyi_10_old
#include <bits/stdc++.h>
using namespace std;
void read(int &x){
int s=0,w=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
w=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
s=s*10+c-'0';
c=getchar();
}
x=s*w;
return;
}
int ans,n,m,a[5000010],k,t;
void f(int l,int r){
int i=l,j=r,p=a[(l + r) / 2];
do {
while (a[i] < p) i++;
while (a[j] > p) j--;
if(i <= j) swap(a[i++],a[j--]);
} while (i <= j);
//a[i]=p;
if(j < k && k < i){
ans=a[k];
//printf("%d",ans);
//exit(0);
return;
}
if (k <= j){
f(l,j);
}
else if (k >= i) {
f(i,r);
}
}
int main(){
read(n);
read(k);
k++;
for(int i=1;i<=n;i++){
read(a[i]);
}
f(1,n);
printf("%d",ans);
system("pause");
return 0;
}