萌新不会写题解，凑和着看吧~ （没抄题解，没抄题解，没抄题解！,且已AC）

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000001];
bool cmp(int x,int y){
    return x > y;
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    sort(a+1,a+n+1,cmp);
    cout << a[m];
    return 0;
}

一个赞拿走~~

数据有点水，我这代码都能AC

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=1e6;
ll n,k,a[MAXN+5];
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    cout<<a[n-k+1];
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
long long n,a[1000005],x;
int main()
{
    int k;
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    sort(a+1,a+n+1);
    cout << a[n-k+1];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    nth_element(a, a + k - 1, a + n, greater<int>());
    cout << a[k - 1];
    return 0;
}

yasuo👀️

#include <iostream>
#include <algorithm>
int yasuo(long a,long b){return a>b;}
int main(){
    long n,m,a[1000005]; std::cin>>n>>m;for(int i=0;i<n;i++)std::cin>>a[i];
    std::sort(a,a+n,yasuo); std::cout<<a[m-1]; return 0;}

思路：sort排序后输出第a-k+1项就是第k大的数了。 如过自己写一个函数cmd让sort大到小排序，输出n[k]就可以了

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    int n[a+1];
    for (int i=1;i<=a;i++)
        cin>>n[i];
    sort(n+1,n+a+1);
    cout<<n[a-b+1];
    return 0;
}

本题的数据范围导致主要时间消耗会在输入输出中，加上输入输出优化后，才能看出下面两个程序的差距。

ios::sync_with_stdio(false);
cin.tie(0);

找第 $k$ 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 $k$ 大的位置的元素。这样做的时间复杂度是 $O(n\log n)$，对于这个问题来说很不划算。

我们可以借助快速排序的思想解决这个问题。考虑快速排序的划分过程，在快速排序的「划分」结束后，数列 $A_{p} \cdots A_{r}$ 被分成了 $A_{p} \cdots A_{q}$ 和 $A_{q+1} \cdots A_{r}$，此时可以按照左边元素的个数（$q - p + 1$）和 $k$ 的大小关系来判断是只在左边还是只在右边递归地求解。

和快速排序一样，该方法的时间复杂度依赖于每次划分时选择的分界值。如果采用随机选取分界值的方式，可以证明在期望意义下，程序的时间复杂度为 $O(n)$。

std::sort，$O(N\log N)$

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1123456];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    k = n - k + 1; //第 k 大 -> 第 new_k 小
    sort(a + 1, a + n + 1);
    cout << a[k] << "\n";
    return 0;
}

快排思想求第 k 大数，$O(N)$

#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[1000000+5]; 
//对 a[l]~a[r] 进行快速排序 ，只需要保证 a[k] 是正确的 
void quick_sort(int l,int r,int k){
	//边界条件 
	if(l>=r) //只有一个元素或者区间不合法 
		return; 
    //可选操作：更换基准数（下面演示的是换成中间的数作为基准）
	int mid = (l+r)/2;
	swap(a[l],a[mid]);
	//挑一个基准数
	int key = a[l];
	//划分左右：左边小于等于key，右边大于等于key
	int pl = l, pr = r;
	while(pl<pr)//还没有都指到空穴 
	{	
		// ( ) x x x x x
		//  pl         pr
		// 找到右边下一个比 key 小的，放在 pl 的位置
		while(pr>pl&&a[pr]>=key)
			pr--;
		a[pl]=a[pr];
		//  x x x ( ) x x
		//  pl     pr
		// 找到左边下一个比 key 大的，放在 pr 的位置
		while(pl<pr&&a[pl]<=key)
			pl++;
		a[pr]=a[pl];
	}
	//(划分好后：a[l~pl-1]<=a[pl/pr]<=a[pr+1~r]) 
	//  x x x (   ) x x
	//        pl/pr
	a[pl] = key;
	//分别对左右进行快速排序
	if(l<=k && k<=pl-1) 
		quick_sort(l,pl-1,k);
	else if(pr+1<=k && k<=r)
		quick_sort(pr+1,r,k);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    k = n - k + 1; //第 k 大 -> 第 new_k 小
    quick_sort(1, n, k); //对 a[1]~a[n] 进行排序，只需要保证 a[k] 正确即可 
    cout << a[k] << "\n";
    return 0;
}

时间差距

std::sort、$O(N\log N)$

快排思想求第 k 大数，$O(N)$

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int n,m;
   cin>>n>>m;
   int n[n+1];
   for (int i =1;i<=n;i++)
      cin >> a[i];
   sort(a + 1,a + n + 1);
   cout << a[n - m + 1];
   return 0;
}

最后一题最简单~不会的纯粹就是”菜“ 😕