目錄

• 問題描述
• 思路與代碼
• • 1. 個(gè)人解法
  • 2. 官方題解

為青白江等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及青白江網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)、做網(wǎng)站、青白江網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！問題描述

原題鏈接🔗：4653. 數(shù)位排序

小藍(lán)對(duì)一個(gè)數(shù)的數(shù)位之和很感興趣，今天他要按照數(shù)位之和給數(shù)排序。

當(dāng)兩個(gè)數(shù)各個(gè)數(shù)位之和不同時(shí)，將數(shù)位和較小的排在前面，當(dāng)數(shù)位之和相等時(shí)，將數(shù)值小的排在前面。

例如， 2022 2022 2022 排在 409 409 409 前面，因?yàn)? 2022 2022 2022 的數(shù)位之和是 6 6 6，小于 409 409 409 的數(shù)位之和 13 13 13。

又如， 6 6 6 排在 2022 2022 2022 前面，因?yàn)樗鼈兊臄?shù)位之和相同，而 6 6 6 小于 2022 2022 2022。

給定正整數(shù) n n n， m m m，請(qǐng)問對(duì) 1 1 1 到 n n n 采用這種方法排序時(shí)，排在第 m m m 個(gè)的元素是多少？

輸入格式
輸入第一行包含一個(gè)正整數(shù) n n n。

第二行包含一個(gè)正整數(shù) m m m。

輸出格式
輸出一行包含一個(gè)整數(shù)，表示答案。

數(shù)據(jù)范圍
對(duì)于 30% 的評(píng)測(cè)用例， 1 ≤ m ≤ n ≤ 300 1≤m≤n≤300 1≤m≤n≤300。
對(duì)于 50% 的評(píng)測(cè)用例， 1 ≤ m ≤ n ≤ 1000 1≤m≤n≤1000 1≤m≤n≤1000。
對(duì)于所有評(píng)測(cè)用例， 1 ≤ m ≤ n ≤ 1 0 6 1≤m≤n≤10^6 1≤m≤n≤106。

輸入樣例：

13
5

輸出樣例：

3

樣例解釋
1 1 1 到 13 13 13 的排序?yàn)椋? 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 個(gè)數(shù)為 3 3 3。

思路與代碼 1. 個(gè)人解法

使用有序的鍵值對(duì)容器map，其中key是每個(gè)數(shù)字的數(shù)位之和，value是符合相應(yīng)數(shù)位之和的所有數(shù)字。例如，當(dāng)key = 1時(shí)，相應(yīng)的value = [1, 10, 100, ...]，用vector容器來(lái)存儲(chǔ)。

因?yàn)槭菑男〉酱蟊闅v的，所以總可以保證兩個(gè)數(shù)字的數(shù)位之和相同時(shí)，大數(shù)在小數(shù)后面。

AC代碼：

#include#include#include

2. 官方題解

方法是自定義排序規(guī)則。

需要注意的是，我們?cè)诒容^兩個(gè)數(shù)的大小的時(shí)候不能現(xiàn)場(chǎng)去計(jì)算它們的數(shù)位之和再去比較，否則會(huì)TLE。必須先預(yù)處理出所有數(shù)字的數(shù)位之和，然后再進(jìn)行排序（因?yàn)榕判虻臅r(shí)間復(fù)雜度是 O ( n log ? n ) O(n\log n) O(nlogn)，所以光是排序就要算 2 × 1 0 7 2\times 10^7 2×107 次，而求一個(gè)數(shù)的數(shù)位之和要算 6 6 6 次，如果現(xiàn)場(chǎng)計(jì)算的話，則總共要算 1.2 × 1 0 8 1.2\times 10^8 1.2×108 次，有可能會(huì)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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：【AcWing寒假每日一題2023】Day8——數(shù)位排序-創(chuàng)新互聯(lián)
文章URL：http://aaarwkj.com/article22/cogdjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、自適應(yīng)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、網(wǎng)站內(nèi)鏈、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)