目录
一、题目
二、解题报告
三、知识风暴
一、题目
1、原题链接
2、题目描述
13
5
3
二、解题报告
1、思路分析
1）创建一个每个元素都是pair类型的数组，其中每个元素记录当前元素的值和当前元素的数位和。
2）根据每个元素的数位和对数组进行排序。
3）输出第m个元素即为所求。
2、时间复杂度
时间复杂度O(n)
3、代码详解
#include
#include
#include
using namespace std;
int ssum(int num){
int sum=0;
while(num){
sum+=num%10;
num/=10;
}
return sum;
}
bool cmp(pair<long long,int> A,pair<long long,int> B){
if(A.second==B.second)
return A.first<B.first;
return A.second<B.second;
}
int main()
{ long long n,m;
cin>>n>>m;
vector<pair<long long,int>> v(n);
for(int i=1;i<=n;i++){
v[i-1].first=i;
v[i-1].second=ssum(i);
}
sort(v.begin(),v.end(),cmp);
cout<<v[m-1].first;
return 0;
}
注：根据sort对pair的默认排序规则，可以简化代码：将每个pair的first存当前元素数位和，second存当前元素的值。这样可以将排序规则省掉，简化代码如下：
#include
#include
#include
using namespace std;
int ssum(int num){
int sum=0;
while(num){
sum+=num%10;
num/=10;
}
return sum;
}
int main()
{ long long n,m;
cin>>n>>m;
vector<pair<long long,int>> v(n);
for(int i=1;i<=n;i++){
v[i-1].first=ssum(i);
v[i-1].second=i;
}
sort(v.begin(),v.end());
cout<<v[m-1].second;
return 0;
}
三、知识风暴
关于pair
