【AcWing寒假每日一题2023】Day8——数位排序-创新互联

问题描述
思路与代码
- 1. 个人解法
- 2. 官方题解

为青白江等地区用户提供了全套网页设计制作服务，及青白江网站建设行业解决方案。主营业务为网站设计、做网站、青白江网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！问题描述

原题链接🔗：4653. 数位排序

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。

当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如， 2022 2022 2022 排在 409 409 409 前面，因为 2022 2022 2022 的数位之和是 6 6 6，小于 409 409 409 的数位之和 13 13 13。

又如， 6 6 6 排在 2022 2022 2022 前面，因为它们的数位之和相同，而 6 6 6 小于 2022 2022 2022。

给定正整数 n n n， m m m，请问对 1 1 1 到 n n n 采用这种方法排序时，排在第 m m m 个的元素是多少？

输入格式
输入第一行包含一个正整数 n n n。

第二行包含一个正整数 m m m。

输出格式
输出一行包含一个整数，表示答案。

数据范围
对于 30% 的评测用例， 1 ≤ m ≤ n ≤ 300 1≤m≤n≤300 1≤m≤n≤300。
对于 50% 的评测用例， 1 ≤ m ≤ n ≤ 1000 1≤m≤n≤1000 1≤m≤n≤1000。
对于所有评测用例， 1 ≤ m ≤ n ≤ 1 0 6 1≤m≤n≤10^6 1≤m≤n≤106。

输入样例：

13
5

输出样例：

样例解释
1 1 1 到 13 13 13 的排序为： 1 , 10 , 2 , 11 , 3 , 12 , 4 , 13 , 5 , 6 , 7 , 8 , 9 1,10,2,11,3,12,4,13,5,6,7,8,9 1,10,2,11,3,12,4,13,5,6,7,8,9。

第 5 5 5 个数为 3 3 3。

思路与代码 1. 个人解法

使用有序的键值对容器map，其中key是每个数字的数位之和，value是符合相应数位之和的所有数字。例如，当key = 1时，相应的value = [1, 10, 100, ...]，用vector容器来存储。

因为是从小到大遍历的，所以总可以保证两个数字的数位之和相同时，大数在小数后面。

AC代码：

#include#include#includeusing namespace std;

map>d;

int sum(int n) {int res = 0;
    for (int i = n; i; i /= 10) res += i % 10;
    return res;
}

int main() {int n, m;
    cin >>n >>m;
    for (int i = 1; i<= n; i++) d[sum(i)].push_back(i);

    int s = 0, key;
    for (const auto &kv: d) {s += (int) kv.second.size();
        if (m<= s) {key = kv.first;
            s -= (int) kv.second.size();
            break;
        }
    }

    cout<< d[key][m - s - 1]<< endl;

    return 0;
}

2. 官方题解

方法是自定义排序规则。

需要注意的是，我们在比较两个数的大小的时候不能现场去计算它们的数位之和再去比较，否则会TLE。必须先预处理出所有数字的数位之和，然后再进行排序（因为排序的时间复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn)，所以光是排序就要算 2 × 1 0 7 2\times 10^7 2×107 次，而求一个数的数位之和要算 6 6 6 次，如果现场计算的话，则总共要算 1.2 × 1 0 8 1.2\times 10^8 1.2×108 次，有可能会TLE）。

#include#include 

using namespace std;

const int N = 1e6 + 10;

struct Node {int val, sum;
} a[N];

bool cmp(const Node &x, const Node &y) {return x.sum< y.sum || x.sum == y.sum && x.val< y.val;
}

int main() {int n, m;
    cin >>n >>m;

    for (int i = 1; i<= n; i++) {a[i].val = i;
        for (int j = i; j; j /= 10) a[i].sum += j % 10;
    }

    sort(a + 1, a + n + 1, cmp);
    cout<< a[m].val<< endl;

    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：【AcWing寒假每日一题2023】Day8——数位排序-创新互联
网站URL：http://6mz.cn/article/cogdjc.html

网站建设知识

【AcWing寒假每日一题2023】Day8——数位排序-创新互联

其他资讯