[Luogu2022] 有趣的数

摘要

题意：Q(N,K) 表示把 1-N 按字典序从小到大排列后 K 的排名。给出 K,M，最小化 N，且 Q(N,K)=M. 无解输出 0。

一道思路很清奇的题。首先可以想到这些结论：

1. 关于 i 单调递增（非严格）
2. 排名一定为 i+1

有了上面的结论，意味着 K 是有最小排名的。即 1-K 必然是要考虑的。考虑字典序比 K 小的数，当 K=345 时，枚举一下：

1. 1-3
2. 10-34
3. 100-345

即当 时，K 的最小排名为

计算上式的复杂度是 的

然后通过比较 m 和最小排名的大小可以判断是否无解。那么如果 m 比最小排名还大，说明 N>K。则我们可以继续枚举，方法与上面的类似：

1. 1000-3449
2. 10000-34449

如果枚举的个数累加起来大于等于 m，说明找到解了，于是输出即可（解的位置可以 O(1) 计算）

总复杂度 （和答案的对数有关）

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int k,m;
int a[20],la;
signed main(){
    scanf("%lld%lld",&k,&m);
    int x=0,k2=k,m10=1;
    while(k2)a[++la]=k2%10, k2/=10;
    reverse(a+1,a+la+1);
    for(int i=1;i<=la;i++){k2=k2*10+a[i];
        x+=k2-m10+1;
        m10*=10;
    }
    if(la==x&&m!=x)return puts("0"),0;
    if(x>m)return puts("0"), 0;
    if(x==m)return printf("%lld",k), 0;
    while(x<m){
        k2*=10;
        int d=k2-m10;// 不含 k2 本身
        if(x+d<m)x+=d;
        else return printf("%lld",m10+m-x-1), 0;
        m10*=10;
    }
    return 0;
}