自动搬运

查看原文

来自洛谷，原作者为

	Akashicw **

搬运于2025-08-24 21:33:03，当前版本为作者最后更新于2017-11-06 23:12:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先感谢一下王乃广老师的耐心讲解！

其次感谢一下@友邻牧鸡同学的指正。

考虑特殊的数字:1,10,100...

可以发现，无论n取何值(n足够大)，我们均可得出第一条结论:10^n(n>=0)总是会排在i+1号位置上。

定义一个数组mi[i]表示排在第i位上的最大数值，显然一定为10^n(n>=0)。

在草稿纸上枚举一下，我们可以得出第二条结论:对于给出的k，随着n的增加，q(n,k)的值总是不下降的。

注：q(n,k)的意义同题目给出，为k在n个数中的位置。

那么我们可以计算出k的最小位置，定义为base。

怎么求base呢？枚举一下排在k前边的数字（包括自己）！

例如：k=234。

• 一位数：1,2(2)-> 2-1+1=2;

• 两位数：10~23(14) ->23-10+1=14;

• 三位数：100~234(135) ->234-100+1=135;

###有没有发现什么？

我们可以一位一位计算，只需要将当前的前n位数字，减去10^(n-1)后加1(别忽略10^(n-1))。最后再累加。

接下来拿base与m作比较，

• 如果base==m，那么我们的结果就恰好为k。

• 如果base>m，那么肯定不存在满足条件的n，直接输出0。

• 如果m>base，要在k=234之前增加m-base个元素。

注意，由于按照字典序排序，我们增加的元素，只能从这n位数的第n+1位(10^(n+1))开始枚举，还是拿234做例子。

增加元素的过程，和之前求k的最小位置是类似的。

• 四位数：1000~2339(1340)个元素。

如果仍然达不到m，我们再让m减去刚才增加的元素个数，继续枚举五位数，这样是乘10地枚举的，速度是对数级别的，可以跑得很快。

那么，如何统计答案呢？

因为从234以后的三位数即使加进去也不影响234之前的排序，所以我们可以这样做：

答案记录当前枚举的位数（记为x）的前一位所有的数字，也就是10^x-1个数字（在这里我们一开始先不删除，最后一并处理）。

如果当前的位数还不符合，就继续枚举下一位。ans乘10。

直到枚举的数字大于了m，我们再让结果加上m减去1(正如之前所说，乘上10的时候，包括了当前一位的10^x，需要删除)，就是ans啦~

代码如下(copy了一下老师的)：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int k,m;
int base,len;
long long mi[20];
long long ans;
//计算k的最小位置 
int calc(int k){ 
    char s[12];
    sprintf(s,"%d",k);
    int ans=0,w=0;
    len=strlen(s);
    for(int i=0;i<len;i++)
    {
        w=w*10+s[i]-'0';
        ans+=w-mi[i]+1;
    }
    return ans; 
}
int main()
{
    mi[0]=1;
    for(int i=1;i<19;i++) mi[i]=mi[i-1]*10;
    scanf("%d%d",&k,&m);
    //1,10,100的位置是固定的 
    for(int i=0;i<10;i++){
        if(k==mi[i]&&m!=i+1){
            printf("0\n"); return 0;
        }
    }
    base=calc(k);
    if(m<base){
        printf("0\n"); return 0;
    }
    if(m==base){
        printf("%d\n",k); return 0;
    }
    ans=mi[len];
    m-=base;
    for(int i=1;;i++)
    {
        long long tmp=k*mi[i]-mi[len+i-1];
        if(m>tmp)
        {
            m-=tmp; 
            ans*=10;
        }
        else break;
    }
    ans+=m-1;
    cout<<ans<<endl;
    return 0;
}