ZOJ Problem Set - 4085

补的很久以前一场比赛的题

题意：

设一个函数 $Q$Q: $Q(n,k)=m$Q(n,k)=m

​ 代表将 $1$1~ $n$n所有数字按字典序排列，数字 $k$k的排列的位置是 $m$m

现在给你一个 $k$k​和 $m$m​，让你求最小的 $n$n​

思路：

• 如果 $k$k是 $10$10的 $i$i次方；那么下列讨论

  • 如果 $i+1=m$i+1=m 则答案为 $k$k
  • 否则 无解

• 先求出 $1$1~ $k$k之间的字典序小于k的个数；可以for循环求出来

  • 如果个数 $tot\>m-1$tot>m−1 则无解

  • 那么肯定有解，下面构造解

    • 令 $k^{\prime }=k$k′=k
    • 每次在 $k^{\prime }$k′后面加一个 $0$0，假设tot为这次在 $k^{\prime }$k′后面添加 $0$0之前字典序小于 $k$k的个数。再次计算 $1$1~ $k^{\prime }$k′小于 $k$k的个数
    • 如果个数 $\>=m-1$>=m−1,则解在$k’ $之前，且解为 $10^{len-1}+m-1-tot-1$10len−1+m−1−tot−1（ $len为k^{\prime }的位数$len为k′的位数)
    • 否则令 $tot$tot为此时 $1$1~ $k^{\prime }$k′小于 $k$k的个数。返回第二步

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6;
ll k,m,n;
ll Pow10[20];
ll arr[20];
void init()
{
    Pow10[0]=1,Pow10[1]=10;
    for(int i=2;i<19;++i)   Pow10[i]=Pow10[i-1]*10ll;
}
/*
计算1~k中比k小的数有多少个
排列组合的加法原理   一位数，二位数，三位数...len位数字 字典序小于k的个数之和
随后一直在k后面加0 计算比k小的数有多少个
*/
void calc()
{
    ll mid=k;
    int top=0;
    do{
        arr[++top]=mid%10;
        mid/=10;
    }while(mid);
    ll Pretot=0;
    ll Presum=0,ans=0;
    /*特判10的次方*/
    for(int i=0;i<=8;++i)
    {
        if(Pow10[i]==k)
        {
            if(m==i+1)
                printf("%lld\n",k);
            else
                puts("0");
            return ;
        }
    }
    for(int i=top;i;--i)
    {
        Presum=Presum*10+arr[i];
        Pretot+=Presum-Pow10[top-i];
        if(i!=1)
            Pretot++;
    }
    if(Pretot>m-1)
        puts("0");
    else if(Pretot==m-1)
        printf("%lld\n",k);
    else{
        /*不停的往后面添加0，记录小于k的个数 并比较答案*/
        for(;;)
        {
            top++;
            Presum*=10ll;
             if(Pretot+Presum-Pow10[top-1]>=m-1)
             {
                 ans=Pow10[top-1]+m-1-Pretot-1;//还需添加m-1-ans个在Pow10(top-1)后面  因为有最后一个属包括0，所以把再次-1 表示把0算上
                 printf("%lld\n",ans);
                 return ;
                    /*找出答案*/
             }
             Pretot+=Presum-Pow10[top-1];
        }
    }
    return ;
}
int main()
{
    int t;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&k,&m);
        calc();
    }
    return 0;
}