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。

说明

【数据约定】

40%的数据，1<=K,M<=10^5；

100%的数据，1<=K,M<=10^9。

---

我大概是看了题解胡乱搞过得。。

首先手玩玩出如何在给定的集合找到指定位置的数，然后玄学看出单调性开始二分答案，最后要判一堆一堆的东西。。

这个题解写的挺好，只是看了前面我后面就去自己yy了

---

乱搞的代码：

#include <cstdio>

#define ll long long

ll m,k,c=1;

ll get(ll n,ll x,ll d)

{

    ll cnt=0;

    while(233)

    {

        if(n>=d&&n<d*10) break;

        cnt+=x-d;

        x*=10;

        d*=10;

    }

    cnt+=(x>n?n:x)+1-d;

    return cnt;

}

ll get0(ll x)

{

    ll t=x/10,d=1,cnt=0;

    while(t)

        d*=10,t/=10;

    while(x)

    {

        cnt+=x+1-d;

        d/=10;

        x/=10;

    }

    return cnt;

}

int main()

{

    //freopen("data.in","r",stdin);

    //freopen("wr.out","w",stdout);

    scanf("%lld%lld",&k,&m);

    for(ll i=1,f=1;i<=10;i++,f*=10)

    {

        if(k==f&&m!=i)

        {

            printf("0\n");

            return 0;

        }

    }

    int t=get0(k);

    if(t>m)

    {

        printf("0\n");

        return 0;

    }

    else if(t==m)

    {

        printf("%d\n",k);

        return 0;

    }

    m-=t-1;

    ll l=k*10,r=1e18;

    while(c<k) c*=10;

    k*=10;

    if(k-c>m)

    {

        printf("%lld\n",m+c-2);

        return 0;

    }

    while(l<r)

    {

        ll mid=l+r>>1;

        if(get(mid,k,c)>=m)

            r=mid;

        else

            l=mid+1;

    }

    printf("%lld\n",l-1);

    return 0;

}

---

2018.7.9