洛谷【P2022 有趣的数】 题解


题目链接

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);

以上就是这道题的题解

上一篇:453. 最小移动次数使数组元素相等


下一篇:关于vue中深拷贝的惨痛教训