第十三届蓝桥杯省赛 C++ C 组 E 题、Python B组 D题、PythonC组 D 题—— 数位排序（AC）

小咪咪 2023-09-28 23:40 17阅读 0赞

## 1.数位排序 ##

### 1.题目描述 ###

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。

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

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

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

### 2.输入格式 ###

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

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

### 3.输出格式 ###

输出一行包含一个整数, 表示答案。

### 4.样例输入 ###

13  
5

### 5.样例输出 ###

### 6.样例说明 ###

1 到 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 个数为 3 。

### 7.数据范围 ###

1 ≤ m ≤ n ≤ 1 0 6 1 \\leq m \\leq n \\leq 10^\{6\} 1≤m≤n≤106

## 2.解题思路 ##

自定义排序的语法题，没什么好讲的。也可以按数位和分组，不断减去当前组的元素，直到找到第 m m m个元素在第几组，将该组排序输出答案即可。

## 3.Ac\_code ##

C++

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair<int, int> PII;
    #define pb(s) push_back(s);
    #define SZ(s) ((int)s.size());
    #define ms(s,x) memset(s, x, sizeof(s))
    #define all(s) s.begin(),s.end()
    const int inf = 0x3f3f3f3f;
    const int mod = 1000000007;
    const int N = 200010;
    
    int n, m;
    bool cmp(const int x, const  int y)
    {
        
    	int s1 = 0, s2 = 0;
    	int a = x, b = y;
    	while (a) {
        
    		s1 += a % 10;
    		a /= 10;
    	}
    	while (b) {
        
    		s2 += b % 10;
    		b /= 10;
    	}
    	if (s1 > s2) return false;
    	else if (s1 < s2) return true;
    	else return x < y;
    }
    void solve()
    {
        
    	cin >> n >> m;
    	std::vector<int> a(n);
    	std::iota(a.begin(), a.end(), 1);
    	sort(all(a), cmp);
    	cout << a[m - 1] << '\n';
    }
    int main()
    {
        
    	ios_base :: sync_with_stdio(false);
    	cin.tie(nullptr);
    	int t = 1;
    	while (t--)
    	{
        
    		solve();
    	}
    	return 0;
    }

Java

import java.util.*;
    
    public class Main {
        
        static Map<Integer, List<Integer>> map = new HashMap<>();
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            for (int i = 1; i <= n; i++) {
        
                add(check(i), i);
            }
            List<Integer> list = new ArrayList<>(map.keySet());
            Collections.sort(list);
            for (Integer integer : list) {
        
                List<Integer> q = map.get(integer);
                if (m > q.size()) {
        
                    m -= q.size();
                    continue;
                }
                Collections.sort(q);
                System.out.println(q.get(m - 1));
                break;
            }
        }
    
        static void add(int a, int b) {
        
            if (!map.containsKey(a)) map.put(a, new ArrayList<>());
            map.get(a).add(b);
        }
    
        static int check(Integer x) {
        
            int res = 0;
            while (x != 0) {
        
                res += x % 10;
                x /= 10;
            }
            return res;
        }
    }