link:http://poj.org/problem?id=3725

这题很有意思,所有数的排列是按其字典序排序的。题意是未知n,但知道第k位的数

是m,问最小的n是多少。这题想了好久,然后看了别人的思想才自己写了段代码,

比如假如已知n=182,问n的位置是多少,因为n为3位数,当一位数时,比它小的有1

两位数时10-18 三位数时100-181 三者相加就是n的位置

反之亦然,我们可以先求出m所在的位置在哪里,然后和k比较,如果比k小,则位数加一

继续查找位置,直到不能减为止。

code:

#include <stdio.h>
#define LL long long
int k;
LL b[20],a[20];
void init()
{
    int i;
    b[1]=1;
    for(i=2;i<20;i++)
        b[i]=b[i-1]*10;/*1 10~ 100~ ..*/
}
void div(int m)
{
	k=0;
    while(m)
    {
        a[k++]=m%10;
        m/=10;
    }
}/*m的位数*/
int main()
{
    int i,j;
    LL s,t,kk,m;
    init();
    while(scanf("%lld%lld",&kk,&m)!=EOF)
    {
        s=0,t=0;
        div(m);
        /*先计算m的位置与kk进行比较*/
        for(i=1;i<=k;i++)
        {
            s=s*10+a[k-i];
            t+=(s-b[i])+1;
        }/*25 1~2 10~25 = 18*/
        if(kk<t)
            printf("0\n");/*如果m本身的位置就大于看,错误*/
        else if(kk==t)
            printf("%I64d\n",m);
        /*如果kk大于m本身的位置,说明位数要+1*/
        else
        {
            s=kk-t;/*1000-18=982*/
			if(m*b[i-k+1]==b[i])
			{
				printf("0\n");
				continue;
			}
            for(;;)
            {
                if(s<=m*b[i-k+1]-b[i])/*982-150=832 832-1500<0 break*/
                    break;
                else
                {
                    s-=m*b[i-k+1]-b[i];
                    i++;
                }
            }
            s=b[i]+s-1;/*1000+832-1*/
            printf("%I64d\n",s);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation