将1~n个整数按照字典序进行排序

题意：给定一个整数n，给定一个整数k，将1~n个整数按字典顺序进行排序，返回排序后第k个元素。

题目链接：HDU6468

多组输入，T<=100,n<=1e6

分析：这个题和之前做的模拟出栈的性质挺像的，不是你将1-n个数字排好序或者直接算出第k个数时谁，而是模拟题意的炒作，一步步填充，填充到第k个元素结束

可以分成两步来做，首先求出以1,2......9开头的数且小于n的数总共有多少个，并且每算出一个就用k-数目，如果到了某个数不够减了，说明我们要求的那个数就是一这个数开头的，跳出循环。

第二步，一点点来，具体实现就直接看代码吧

我自己写还是错了很多次才最终写对

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf=<<;

const int maxn=;

const double pi=acos(-);

const int mod=1e9+;

int ans=,n,k;

//用来得到比n小，以i为开头的数的数目

int getnum(int n,int i){

    int base=,sum=;

    while(n>=(base*(i+))){

        sum+=base;

        base*=;

    }

    if(n>=(base*i))sum+=n-base*i+;

    return sum;

}

void getans(int &cnt,int cul){

    if(++cnt==k){

        ans=cul;

        return ;

    }

    for(int i=;i<=;i++){//注意，这里是从0开始了

        int t=cul*+i;

        if(t<=n) getans(cnt,t);

        if(cnt>=k) return ;//保证有这一步免得程序重复执行

    }

}

int main(){

    int T;scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&k);

        int i;//注意i不要在for循环里定义

        for(i=;i<=;i++){

            int num=getnum(n,i);

            if(k>num) k-=num;

            else break;

        }

        int cnt=;

        getans(cnt,i);

        cout<<ans<<endl;

    }

    return ;

}