欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

【AcWing寒假每日一題2023】Day8——數(shù)位排序-創(chuàng)新互聯(lián)

目錄
  • 問題描述
  • 思路與代碼
    • 1. 個人解法
    • 2. 官方題解

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

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

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

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

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

又如， 6 6 6 排在 2022 2022 2022 前面，因為它們的數(shù)位之和相同，而 6 6 6 小于 2022 2022 2022。

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

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

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

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

數(shù)據(jù)范圍
對于 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

輸出樣例：

3

樣例解釋
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 個數(shù)為 3 3 3。

思路與代碼 1. 個人解法

使用有序的鍵值對容器map，其中key是每個數(shù)字的數(shù)位之和，value是符合相應數(shù)位之和的所有數(shù)字。例如，當key = 1時，相應的value = [1, 10, 100, ...]，用vector容器來存儲。

因為是從小到大遍歷的，所以總可以保證兩個數(shù)字的數(shù)位之和相同時，大數(shù)在小數(shù)后面。

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. 官方題解

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

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

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

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

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

廣告

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

網(wǎng)站優(yōu)化排名