题解 | #字典序#

使用字典树，依次统计以pre为前缀是否能够满足m个数的需求(pre首先取1),如果能够满足个数需求，说明前缀应该是pre，把pre固定下来，在pre的后面加最小的一个0再继续统计。如果不能够满足个数需求，说明以pre为前缀的数还不够，还需要以pre+1为前缀的数，依次统计直到刚好满足个数需求。

#include <iostream>
using namespace std;

//获取以pre为前缀，不大于n的数的个数，前缀pre也算是一个数;
long get_cnt_of_pre(long pre, long n)
{
    long count = 1;
    long p = 10;
    do
    {
        long left = pre*p;                //以pre为前缀，最左边的子节点的数;
        long right = pre*p+p-1;           //以pre为前缀，最右边的子节点的数;
        if(left > n)
        {
            //若最左边的子节点都比n大，说明应该结束;
            break;
        }
        if(n >= right)
        {
            //n比最右边的数大，说明还没有找到最后一行，将当前行所有数都统计进去;
            //当前行有p个数;
            count += p;
        }else {
            //n没有比最右边的数大，说明已经找到了最后的一行;
            //最后一行只能统计left到n的个数;
            count += (n - left) + 1;
            break;
        }
        //定位到下一行;
        p*=10;
    }while(true);

    return count;
}

long solve(long n, long m)
{
    long pre = 1;
    while(true)
    {
        long cnt = get_cnt_of_pre(pre,n);
        if(cnt >= m)
        {
            //以pre为前缀能够满足m个数的需求;
            //前缀也算是一个数,m减少1;
            m--;
            if(m==0)
            {
                //统计的个数刚好为m时结束统计;
                break;
            }

            //在pre后面添加一个0继续探索;
            pre *= 10;
        }else {
            //以pre为前缀不能够满足m个数的需求;
            //m减少以pre为前缀的个数;
            m-=cnt;
            //以pre+1为前缀继续探索;
            pre++;
        }
    }
    return pre;
}

int main()
{
    long n,m;
    cin >> n >> m;
    cout << solve(n,m);

    return 0;
}