小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。
当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？
输入格式
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
输出格式
输出一行包含一个整数，表示答案。
数据范围
对于 30% 的评测用例，1≤m≤n≤300。
对于 50% 的评测用例，1≤m≤n≤1000。
对于所有评测用例，1≤m≤n≤106。
输入样例：
13 5
输出样例：
3
样例解释
1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。
第 5 个数为 3。
我的思路：
- 对于50%的样例，是可以用暴力枚举的
- 首先，开一个长度为106的数组，用来存储排序后的每一个数
- 这里采用输入的同时排序，时间复杂度是够用的
排序使用可以降低复杂度的二分算法 - 排好之后直接输入m位置上的数即可
对于50%样例的代码：
#include<iostream> using namespace std; const int N = 1e6+10; int a[N]; int position(int i, int len){ if(len == 0) return 1; int sum = 0, cnt = i; while(cnt){ sum += cnt%10; cnt /= 10; } int low = 1, high = len, mid; while(low <= high){ mid = (low+high)/2; int sum_mid = 0, cnt_mid = a[mid]; while(cnt_mid){ sum_mid += cnt_mid%10; cnt_mid /= 10; } if(sum > sum_mid || (sum == sum_mid && i > a[mid])) low = mid+1; else if(sum < sum_mid || (sum == sum_mid && i < a[mid])) high = mid-1; } return low; } int main(){ int n, m, k = 0; cin >> n >> m; for(int i = 1; i <= n; i++, k++){ int index = position(i, i-1); for(int j = i-1; j >= index; j--){ a[j+1] = a[j]; } a[index] = i; } cout << a[m]; return 0; }
查找位置的复杂度为O(nlog2n)，所有总的复杂度为O(n2log2n)，对于所有的样例肯定会TLE
优化思路：
- 对于上面的106长度的数组，进行改进
- 由于所有数所能产生的数位和的数量是有限的，所以可以考虑用散列表的形式进行存储
对于每一个数，用所得到的数位和作为散列地址 - 利用拉链法，使得相同数位和的数（同义词）存储在同一散列地址的链表下
- 对于同一个数位和的不同数，后面来的一定比前面来的要大，所以可以不用链表，直接用数组
代码：（可以AC）
#include<iostream> #include<vector> #include<map> using namespace std; map<int, vector<int> > dic; int main(){ int n, m, k = 0, len = 0; cin >> n >> m; for(int i = 1; i <= n; i++){ int cnt = i, sum = 0; while(cnt){ sum += cnt%10; cnt /= 10; } if(dic.find(sum) == dic.end()){ dic[sum] = vector<int>(0); } dic[sum].push_back(i); } //对于map的遍历有点忘了 //下面这段代码来源：https://www.acwing.com/solution/content/159370/ for (const auto &i: dic){ if (m > i.second.size()) m -= i.second.size(); else{ cout << i.second.at(m - 1); break; } } return 0; }
y总的思路：
- 基本上算是用时间换空间，加一个排序、查找
- 对于每一个数，存储下这个数的数位和
- 根据这个数位和对1~n进行排序
- 最后只需查找出第m个位置的数
代码：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1000010; int n, m; int w[N], s[N]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { w[i] = i; for (int j = i; j; j /= 10) s[i] += j % 10; } sort(w + 1, w + n + 1, [&](int a, int b) { if (s[a] != s[b]) return s[a] < s[b]; return a < b; }); printf("%d\n", w[m]); return 0; } //作者：yxc //链接：https://www.acwing.com/activity/content/code/content/5088776/ //来源：AcWing //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
提示： 对于这道题的数据范围，如果在排序的同时进行计算数位和，会使得计算量上升一个量级。因为最快的排序也需要O(nlogn)的时间复杂度，所以需要先存下所有数的数位和，不然会TLE。
