【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：https://www.cdcxhl.com/article22/cogdjc.html

成都网站建设公司_创新互联，为您提供搜索引擎优化、自适应网站、手机网站建设、企业网站制作、网站内链、App设计

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容