題目描述
給定整數n和m, 將1到n的這n個整數按字典序排列之后, 求其中的第m個數。
對于n=11, m=4, 按字典序排列依次為1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4個數是2.

輸入描述:
輸入僅包含兩個整數n和m。

數據范圍:

對于20%的數據, 1 <= m <= n <= 5 ;

對于80%的數據, 1 <= m <= n <= 10^7 ;

對于100%的數據, 1 <= m <= n <= 10^18.
輸出描述:
輸出僅包括一行, 即所求排列中的第m個數字.

C++代碼：

//主要采用字典樹的思想 #include<iostream> using namespace std;long get_num(long long k,long long n){long long base=1,count=0;while((k+1)*base-1<=n){count+=base;base*=10;}if(k*base<=n)count+=n-k*base+1;return count; } long long ans(long long n,long long m){long long k=1;while(m){long long count=get_num(k,n);if(count>=m){m--;if(!m) break;k*=10;} else{k++;m-=count;} }return k; } int main(){long long n,m;cin>>n>>m;cout<<ans(n,m)<<endl;return 0; }

總結

以上是生活随笔為你收集整理的今日头条——校招在线编程题《字典序》的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。