题目链接
https://www.luogu.org/problem/P2022
题目描述
让我们来考虑1到N的正整数集合。让我们把集合中的元素按照字典序排列，例如当N=11时，其顺序应该为：1,10,11,2,3,4,5,6,7,8,9。
定义K在N个数中的位置为Q(N,K)，例如Q(11,2)=4。现在给出整数K和M，要求找到最小的N，使得Q(N,K)=M。
输入格式
输入文件只有一行，是两个整数K和M。
输出格式
输出文件只有一行，是最小的N，如果不存在这样的N就输出0。
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
long long k, m, i = 0, j, l = 0, a[30], b = 0, d, c, e, n = 0, aa = 0, bb;
cin >> k; //输入k
cin >> m; //输入m
c = k; //将k赋给c，不让k变化
while (c) //将k存到数组a[]里
{
a[i] = c % 10;
c = c / 10;
i++;
}
b = 0;
e = i;
d = e;
for (d; n <= i + 1; d--)
{
for (j = 1; j <= d; j++)
{
l = pow(10, j - 1) + l;
}
if (n == 0)
b = (a[i - 1 - n] - 1)*l + b;
else
b = a[i - 1 - n] * l + b;
n++;
l = 0;
}
b = b + i;//最小值为k时，k的排名
if (b == m) {
cout << k;
}
else if (m < b) { cout << 0; }
else
for (e = i;;e++)
{
bb = k * pow(10, e - i + 1) - pow(10, e) + aa;
if (m - b <= bb)
{
cout << setprecision(30) << m - b - 1 - aa + pow(10, e);
break;
}
aa = k * pow(10, e - i + 1) - pow(10, e) + aa;
}
return 0;
}
方法
先考虑当最大的整数为k时，k的位置。 代码如下：
for (d; n <= i + 1; d--) { for (j = 1; j <= d; j++) { l = pow(10, j - 1) + l; } if (n == 0) b = (a[i - 1 - n] - 1)*l + b; else b = a[i - 1 - n] * l + b; n++; l = 0; } b = b + i;//最小值为k时，k的排名
其中数组a[ ]里存着k
这段代码的讲解如下，为方便理解，令k=453，则有四种数字在k前边：
- （1）首位以1、2、3开头的数字，个数为（1+10+100）×（4-1）
- （2）首位为4的数，次位小于5的数，个数为(1+10)×（5-0)+1
- （3）首位为4，次位为5，第3位小于3的数，个数为1×（3-0）
- （4）首位或第二位与K相同，但总位数小于k。两个，分别为4、45
通过这种方法就求出来了最大值为k时的排名b。
- 如果m=b，那显然最小值n=k;
- 如果m<b，则不存在n，因为该组数的最小值肯定是>=k的。
- 如果m>b,则一定存在n。
下面讨论m>b的情况。
分析易知，若m>b,则n的位数肯定大于k的位数。K=453有3位，分析知4位数里排在453前边的数字有：
- 1000-1999,2000-2999,3000-3000,4000-4529
数字的数量 用代码表示为
453*pow(10,4-3+1)-pow(10,4) //pow(10,4-3+1)中的4代表4位数 3代表K的位数，pow(10,4)里的4代表4位数
若
- （m-3位数字中k的排名）<4位数里排在453前边的数字个数时
- 则所求数字n必然为四位数字，且n在1000-1999,2000-2999,3000-3000,4000-4529范围内
- n=（m-3位数字中k的排名-1）+1000。 若
- （m-3位数字中k的排名）>4位数里排在453前边的数字个数，则应继续判断（m-4位数字中k的排名）与5位数里排在453前边的数字个数大小，直到 （m-i位数字中453的排名）<与(i+1)位数里排在453前的数字量，此时即可得到所求的最小数字
- n=(m-i位数字中453的排名-1）+pow(10, i);
以上就是这道题的题解