【蓝桥杯2022省赛】蓝桥杯2022省赛数位排位、求阶乘
【蓝桥杯2022省赛】蓝桥杯2022省赛数位排位、求阶乘
目录
一、数位排序
问题描述
小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。 例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6, 小于 409 的数位 之和 13 。 又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。 给定正整数 n,m, 请问对 1 到 n 采用这种方法排序时, 排在第 m 个的元 素是多少?
输入格式
输入第一行包含一个正整数 n 。
第二行包含一个正整数 m 。
输出格式
输出一行包含一个整数, 表示答案。
样例输入
13
5样例输出
3样例说明
1 到 13 的排序为: 1,10,2,11,3,12,4,13,5,6,7,8,91,10,2,11,3,12,4,13,5,6,7,8,9 。第 5 个数为 3 。
评测用例规模与约定
对于 30% 的评测用例, 1≤m≤n≤300 。
对于 50% 的评测用例, 1≤m≤n≤1000 。
对于所有评测用例, 1≤m≤n≤10e6 。
运行限制
- 最大运行时间：3s
- 最大运行内存: 512M
问题解析
题目要求：当两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。输出排在第m的数字 解题思路：可以计算数字的位数，对于位数进行排位。例如数组为[11,12,2]，排位后为[2,11,12]。上述操作我们如果自定义函数的话可能比较麻烦。但是在对数组排序时，我们可以使用Array.sort(数组,(类1,类2）->...)书写排序标准。最终通过率也是100%。 具体代码如下.
解题代码
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
//输入n,m
int n=scan.nextInt(),m=scan.nextInt();
//此处定义Integer数组，方便后面进行排序
Integer[] arr=new Integer[n];
//输入数组元素
for(int i=0;i<n;i++){
arr[i]=i+1;
}
//对数组进行排序 如果相同则升序排序，若不同按数位小的排在前面
Arrays.sort(arr,(a,b)->number(a)!=number(b) ? number(a)-number(b):a-b);
System.out.println(arr[m-1]);
scan.close();
}
//定义函数计算数字数位.(注意此处必需设置为static,否则运行时报错)
public static int number(Integer i){
int res=0;
//利用循环计算函数各数位相加和
while(i!=0){
res+=i%10;
i/=10;
}
return res;
}
}
二、求阶乘
问题描述
满足 N ! 的末尾恰好有 K 个 0 的最小的 N 是多少? 如果这样的 N 不存在输出 −1−1 。
输入格式
一个整数 K 。
输出格式
一个整数代表答案。
样例输入
2样例输出
10评测用例规模与约定
对于 30%的数据, 1≤K≤10e6.
对于 100% 的数据, 1≤K≤10e18.
运行限制
- 最大运行时间：3s
- 最大运行内存: 512M
问题解析
题目要求：满足 N ! 的末尾恰好有 K 个 0 的最小的 N 是多少?如果这样的 N 不存在输出 −1 。 解题思路：直接算出 又k个0的N!很难。N! 末尾的 0 取决于1 到 N 各因子2 和 5 的组合个数，但是实际上5的个数小于2的个数，所以末尾0的个数实际取决于 5 的个数。所以我们可以统计 1 到 N 中 5 的倍数个数，复杂度为 O(logN)。又因为 N 越大，末尾的 00 越多，所以可以用二分找到答案。
解题代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
//输入的数字应为long。原因是阶乘算出的结果较大，用int会溢出。
long k=scan.nextLong();
long left=0,right=Long.MAX_VALUE;
//利用二分查找，找到符合0个数的最小数字
while(left<right){
long mid=left+(right-left)/2;
if(zero(mid)<k)left=mid+1;
else right=mid;
}
//此时left就是我们求出的结果
long res=zero(left);//可能不为k。
if(res==k)System.out.println(left);//若和k相等，则是找到了数字left的阶乘结果又k个0。
else System.out.println(-1);//不相等则返回-1;
scan.close();
}
public static long zero(long n){
long res=0;//计算数字含5的个数。
while(n!=0){
res+=n/5;
n/=5;
}
return res;
}
}计算含5的个数例子： 25->(5,1),(10,1),(15,1),(20,1),(25,2)------->6
