模拟法
暴力法的思路就是开一个长度为 $n$ 的数组 arr
,存储 $1 \sim n$,然后在按照题意自定义一个比较函数 cmp
,对 arr
进行一次自定义排序,最后返回 arr[m-1]
#include <bits/stdc++.h>
using namespace std;
inline int help(int a){ //计算a的数位和
int ans=0;
while(a){
ans+=a%10;
a/=10;
}
return ans;
}
bool cmp(int a,int b){ //自定义比较函数
int x=help(a),y=help(b);
if(x!=y) return x<y;//数位和小的排前面
else return a<b;//若数位和相同,让数值小的排前面
}
int main(){
int m,n;
cin>>n>>m;
vector<int> arr(n);
iota(arr.begin(),arr.end(),1);//填充arr,即arr[i]=i+1
sort(arr.begin(),arr.end(),cmp);
cout<<arr[m-1];
return 0;
}
最终结果超时,考虑进行优化
容易发现,我们在自定义排序的过程中,会多次计算某个数的数位和(也就是重复计算),因此考虑“空间换时间”,在填充 arr
的过程中直接计算出数 i
的数位和,然后再去排序。
$tip:$这里可以直接用 pair<int,int>
来存储数据,其中:
first
存储i
的数位和second
存储i
本身
这样的好处是,当我们调用 sort
函数时,默认就会先根据 first
的大小进行比较,若 first
相同,再才会比较 second
,这恰好与题目的要求是一致的。
#include <bits/stdc++.h>
using namespace std;
inline int help(int x) {
int ans = 0;
while (x) {
ans += x % 10;
x /= 10;
}
return ans;
}
int main() {
int m, n;
cin >> n >> m;
vector<pair<int, int> > arr(n + 1);
for (int i = 1; i <= n; i++) {
arr[i].second = i;
arr[i].first = help(i);
}
sort(arr.begin(),arr.end());
cout<<arr[m].second;
return 0;
}
-
时间复杂度:
-
由于 $n < 10^6$,因此
help()
的时间复杂度可近似认为是 $O(1)$,因此计算 $1\sim n$ 的数位和需要的时间复杂度为$O(n)$ - 排序过程需要的时间复杂度为 $O(nlogn)$
因此总时间复杂度为$O(nlogn)$
-
空间复杂度:
-
存储 $1\sim n$ 的数位和需要的空间复杂度为$O(n)$
- 排序过程需要的栈空间为 $O(logn)$
因此总空间复杂度为:$O(n)$
👀