用nth_element
库函数
一、作用
查找第n
小的元素
二、用法
nth_element
(起始地址,查找元素的下标,最后一个元素地址+1);
nth_element
(起始地址,查找元素的下标,最后一个元素地址+1,自定义排序);
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N],m,n;
int get_sum(int x)
{
int res = 0;
while(x)
{
res += x % 10;
x /= 10;
}
return res;
}
bool cmp(int a,int b)
{
int t1 = get_sum(a);
int t2 = get_sum(b);
if(t1 == t2)return a < b;
else return t1 < t2;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)q[i] = i;
nth_element(q + 1,q + m,q + n + 1,cmp);
cout << q[m];
}
快速排序变形
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N],m,n;
int get_sum(int x)
{
int res = 0;
while(x)
{
res += x % 10;
x /= 10;
}
return res;
}
//前面小于后面返回true
bool cmp(int a,int b)
{
int t1 = get_sum(a);
int t2 = get_sum(b);
if(t1 == t2)return a < b;
else return t1 < t2;
}
void quick_sort(int l,int r)
{
if(l >= r)return;
int x = q[l+r>>1],i = l-1,j = r + 1;
while(i < j)
{
do j --;while(cmp(x,q[j]));
do i ++;while(cmp(q[i],x));
if(i < j)swap(q[i],q[j]);
}
if(m >= j + 1)quick_sort(j + 1,r);
else quick_sort(l,j);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)q[i] = i;
quick_sort(1,n);
cout << q[m];
}