AcWing 4782. 第k个数
原题链接
简单
作者:
虚实相依
,
2024-03-25 21:26:39
,
所有人可见
,
阅读 2
# sort写法:
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int a,b;
int arr[N];
int cmp(int x,int y)
{
return x>y;
}
int main()
{
cin>>a>>b;
for(int i=1;i<=a;i++) cin>>arr[i];
sort(arr+1,arr+1+a,cmp);
cout<<arr[b]<<endl;
return 0;
}
## 归并排序:
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int q[N];
int w[N];
int n,m;
void merge_sort( int l, int r) {
if (l >= r) return;
int mid = l + r >>1;
merge_sort( l, mid), merge_sort(mid + 1, r); //首先划分为两个区间进行排序
int i = l, j = mid + 1, k = 0;//对于每个区间,具体又用mid分隔
while (i <= mid && j <= r)
if (q[i] > q[j]) w[k++] = q[i++];
else w[k++] = q[j++];
while (i <= mid) w[k++] = q[i++];//左边先排好
while (j <= r) w[k++] = q[j++];//右边再排好
for (int i = l,j=0; i <= r; i++,j++) q[i] = w[j];//重新组合
}
int main() {
scanf("%d%d", &n,&m);
for (int i = 1; i <= n; i++) scanf("%d", &q[i]);
merge_sort(1, n);
//for (int i = 1; i <= n; i++) printf("%d ", q[i]);
cout<<q[m]<<endl;
return 0;
}