AcWing 4782. 第k个数
原题链接
简单
作者:
虚实相依
,
2024-04-06 15:05:39
,
所有人可见
,
阅读 4
# 优先队列
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010;
priority_queue<int,vector<int>,less<int>> q;
int n,m;
int main()
{
cin>>n>>m;
int x;
for(int i=1;i<=n;i++)
{
cin>>x;
q.push(x);
}
int num=1;
while(q.size())
{
if(num==m)
{
cout<<q.top()<<endl;
return 0;
}
q.pop();
num++;
}
return 0;
}
## 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);
cout<<q[m]<<endl;
return 0;
}