题目描述
让我们来考虑$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。
输入输出样例
输入样例#1：
2 4
输出样例#1：
11
输入样例#2：
100000001 1000000000
输出样例#2：
100000000888888879
说明
【数据约定】
40%的数据，$1<=K,M<=10^5$；
100%的数据，$1<=K,M<=10^9$。
解题思路
骗分过样例，暴力出奇迹。
首先不难想到特判$K==M$，$K>M$的情况。若$K==M$直接输出$M$，$K>M$输出0。直接输出0也有18分。
接下来我们来思考正解。我们可以先求出小于$M$且字典序小于$M$的数的个数，再计算大于$M$，且字典序小于$M$的数的个数，这样我们就得到了正确答案。
1
|
if(cnt>m-1 || (k==ret && cnt<m-1))
|
这一行是个小剪枝，特判了一下输出0的情况，直接结束。
贴下代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define R register
#define I inline
template<class >void read( &x) {
register ll c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
ll n,k,m;
ll cnt,ret;
ll get(ll m)
{
ll m1=m,m2=m;
ll res=1;
while(m1)
{
m1/=10;
res*=10;
}
res/=10;
ret=res;
while(m2)
{
cnt+=m2-res+1;
m2/=10;
res/=10;
}
cnt--;
return cnt;
}
int main()
{
read(k);read(m);
cnt=get(k);
if(cnt>m-1 || (k==ret && cnt<m-1))
{
printf("0");
return 0;
}
ll c=k,p=k-ret;
while(cnt<m-1)
{
c*=10;
p*=10;
cnt+=p;
}
n=max(k,c+m-cnt-2);
printf("%lldn",n);
return 0;
}
|
近期评论