Acwing-4653. 数位排序

2023-11-17

本题重点在于预处理每个数的各位之和、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;
}

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Acwing-4653. 数位排序 的相关文章