Acwing-4653. 数位排序

本题重点在于预处理每个数的各位之和、cmp函数的书写，根据题目中的描述：当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。不难写出cmp函数。

快速排序的比较次数为nlogn次，本题中约为2*10^7，如果每次都要算这个数的各位之和的话，由于n最大是10^6，也就是6位，再计算6次，总共是2*10^7 * 6 = 1.2 * 10^8 可能会超时。

如何优化呢？我们可以先开个数组s[N]，把1-1000000这些数，每个数的各位之和先存下来，这样的话我们在比较的时候就不用现算了，就可以通过查表的方式查出来每个数的各位之和是多少，查表的话只需要一次运算。注：s[i]表示i的各位数之和是多少。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int w[N], s[N];

bool cmp(int a, int b)
{
    if (s[a] < s[b]) return true;
    if ((s[a] == s[b]) && a < b) return true;
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) 
    {
        w[i] = i;
        int j = i;
        while (j) s[i] += j % 10, j /= 10;
    }
    
    sort(w + 1, w + 1 + n, cmp);
    
    printf("%d", w[m]);
    return 0;
}