小蓝要为一条街的住户制作门牌号。这条街一共有 2020 位住户,门牌号从 1 到 2020 编号。小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符,最后根据需要将字符粘贴到门牌上,例如门牌 1017 需要依次粘贴字符 1、0、1、7,即需要 1 个字符 0,2 个字符 1,1 个字符 7。请问要制作所有的 1 到 2020 号门牌,总共需要多少个字符 2?请将所有数字及数学符号变成中文描述并回答这个问题
时间: 2023-05-28 15:06:25 浏览: 79
小蓝需要制作 0 到 9 这 10 个数字字符,每个字符需要 1 个字符 2,总共需要 10 个字符 2。对于 1 到 2020 号门牌,我们可以将其拆分成 1 到 9 号门牌、10 到 99 号门牌、100 到 999 号门牌和 1000 到 2020 号门牌四个部分。
对于 1 到 9 号门牌,每个门牌只需要 1 个数字字符,即共需要 9 个字符 2。
对于 10 到 99 号门牌,每个门牌需要 2 个数字字符,共 90 个门牌,即共需要 180 个字符 2。
对于 100 到 999 号门牌,每个门牌需要 3 个数字字符,共 900 个门牌,即共需要 2700 个字符 2。
对于 1000 到 2020 号门牌,每个门牌需要 4 个数字字符,共 1021 个门牌,即共需要 4084 个字符 2。
因此,总共需要 9+180+2700+4084=6973 个字符 2。
相关问题
小蓝要为一条街的住户制作门牌号。这条街一共有 2020 位住户,门牌号从 1 到 2020 编号。小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符,最后根据需要将字符粘贴到门牌上,例如门牌 1017 需要依次粘贴字符 1、0、1、7,即需要 1 个字符 0,2 个字符 1,1 个字符 7。请问要制作所有的 1 到 2020 号门牌,总共需要多少个字符 2?
我们可以先统计所有门牌中数字 2 出现的次数,再乘以 1(门牌号中有 1 个数字 2)、2(门牌号中有 2 个数字 2)等不同情况下的门牌数量。对于每个数字,它在个位上出现的次数是 $\lfloor \frac{2020}{10} \rfloor = 202$,在十位上出现的次数也是 202,以此类推。但是需要注意的是,当门牌号为 2000 时,它只算作一个数字,不能被拆成两个 2。因此,我们需要分别计算个位、十位、百位、千位上数字 2 的出现次数,再根据门牌号的不同情况进行计算。具体来说:
- 个位上:共有 $202 \times 1 = 202$ 个数字 2;
- 十位上:共有 $202 \times 10 + (20 - 10) = 2020$ 个数字 2,其中 $10 \sim 19$ 这 10 个数字有 1 个 2,其余数字有 2 个 2;
- 百位上:共有 $202 \times 100 + (200 - 100) \times 2 + 20 = 20420$ 个数字 2,其中 $100 \sim 199$ 这 100 个数字有 1 个 2,其余数字有 2 个 2;
- 千位上:共有 $202 \times 1000 + (2000 - 1000) \times 2 + 200 = 206020$ 个数字 2,其中 $1000 \sim 1999$ 这 1000 个数字有 1 个 2,其余数字有 2 个 2。
因此,数字 2 在所有门牌中出现的次数为 $202 + 2020 \times 2 + 20420 \times 1 + 206020 \times 1 = 429664$。如果门牌号中有 $k$ 个数字 2,那么需要 $k$ 个字符 2,因此总共需要 $1\times 202 + 2 \times 2020 + 3 \times 20420 + 4 \times (2020 - 20) + 4 \times 200 + 5 \times 2 = 143422$ 个字符 2。
小蓝有一个长度为 nn 的数组, 初始时从左到右依次是 1,2,3, \ldots n1,2,3,…n 。
小蓝想要对这个数组进行一些操作,使得最终数组的逆序对数目最小。逆序对指的是在数组中,若 i<j 但 a[i]>a[j],则称 (i,j) 是一个逆序对。
要求:请你给出一个算法,使得操作后的数组逆序对数目最小。并且,给出算法的时间复杂度和空间复杂度,并说明你的算法为什么能保证得到最小的逆序对数目。
思路:这个问题可以直接用归并排序的思想来解决。归并排序的过程中,将两个已经排序的数组合并成一个有序数组的时候需要记录逆序对的数目。具体实现的过程中,可以在合并数组的过程中记录左边数组中大于右边数组中当前元素的个数,从而求出逆序对的数目。
时间复杂度:归并排序的时间复杂度为 O(nlogn),只需要在合并数组的时候顺便统计逆序对的数目,时间复杂度不变。
空间复杂度:归并排序的空间复杂度为 O(n),需要一个额外的数组来存储排序后的结果。
正确性证明:算法的正确性可以用数学归纳法来证明。假设对于长度为 k 的数组能够得到最小的逆序对数目,现在考虑长度为 k+1 的数组。将数组分为左右两个部分,分别排序并统计出左半边有 m 个元素大于右半边的元素,那么左半边中的逆序对数目为 x,右半边中的逆序对数目为 y,则新的逆序对数目为 x+y+m。可以发现,对于左右两半边来说,当前的排序顺序是最小的,因此如果左右两半边中的元素之间存在逆序对,一定是由左半边中的元素和右半边的元素组成的。因此,对于 m,只需要找出左半边中第 m+1 个元素和右半边的元素进行比较,如果左半边的元素比右半边的元素大,逆序对数目可以减少 m,如果左半边的元素比右半边的元素小,则逆序对数目会增加左半边中比这个元素小的元素的个数,即 x+m+1,这样可以保证每次合并数组时逆序对数目最小。