数位排序
思路
此题是一道简单的排序,系统提供的sort函数,时间复杂度在O(N * log(N)), 数据量只有1e6,计算得知时间复杂度为5 * 1000000 = 5e6, 因此方法可行
只需要用数组,存储原数x,再存储数位和y,进行比较即可
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
struct Node
{
int x;
int byteSum;
bool operator < (const Node & w) const
{
if(byteSum < w.byteSum) return true;
else if(byteSum == w.byteSum) {
return x < w.x;
}
else return false;
}
} a[N];
int getSum(int x)
{
int sum = 0;
while(x)
{
sum += x % 10;
x /= 10;
}
return sum;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
a[i].x = i;
a[i].byteSum = getSum(i);
}
sort(a + 1, a + 1 + n);
// for (int i = 1; i <= n; i ++ ) cout << a[i].x << " " << a[i].byteSum << endl;
cout << a[m].x;
return 0;
}