//#pragma G++ optimize("Ofast")
#define fst first
#define sed second
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N=1e6+10;
PII a[N];
int n, m;
int c(int i){
int res=0;
while(i){
res+= i%10;
i/=10;
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++)
a[i]={c(i), i};
nth_element(a+1, a+m, a+1+n);
cout<<a[m].second;
return 0;
}
只是平均时间复杂度 $\Theta (n)$ 吧,最坏情况应该能到 $\Theta (n ^ 2)$
对的
复杂度瓶颈在于$c$函数,总体时间复杂度为$O (nlogn)$
快速选择第n个,$O(n)$