数位排序
题目大意:输入两个数,n,m。
将1~n的数,按照以下规则排序:
当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。
例如,2022 排在 409前面,因为 2022 的数位之和是 6,小于 409 的数位之和 13。
又如,6排在 2022 前面,因为它们的数位之和相同,而 6 小于 2022。
输入第出排序后的第m个数
思路
- 根据两个参数进行排序,可以使用序偶pair
- pair 还被称之为“序偶”,亦即它默认是可以比较的。它以 first 作为第一关键字,second 为第二关键字。
- 当然也可以用结构体存储数和数位和,自定义排序规则即可
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
pair<int ,int> a[N];
int solve(int x){
int sum = 0;
while(x){
sum +=x%10;
x = x/10;
}
return sum;
}
int main(){
int m,n;
cin>>m>>n;
for(int i = 1; i <= m; i ++){
a[i] = {solve(i),i};
}
sort(a+1,a+1+m);
cout<<a[n].second<<endl;
return 0;
}
在编写代码时,发现数组下标就可以代替第几位,用数组存数位和。即用下标代表原数字,数组存的数字代表数位和。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int a[N],b[N];
bool cmp(int x,int y)
{
if(b[x] != b[y]) return b[x] < b[y];
else return x < y;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1; i <=n; i ++)
{
a[i] = i;
int x = i;
while(x)
{
b[i] +=x%10;
x /= 10;
}
}
sort(a+1,a+1+n,cmp);
cout<<a[m]<<endl;
return 0;
}