2024华为OD机试（E卷+D卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

3020年，空间通信集团的员工人数数量突破20亿，现有工号系统不够用的窘境。

现在，请你负责调研新工号系统。继承历史传统，新工号系统由小写英文字母（a-z）和数字（0-9）两部分构成。

新工号分一段英文字符开头，之后跟着一段数字，例如"aaaahw0001"，“a12345”，“abcd1”，“a00”。

注意新工号数字不能全字母或者数字，允许数字部分有前导0或者全为0。

但是过长的工号会增加同事们的记忆成本，现给出新工号至少需要分配的人数X和新工号中字母的长度Y，求新工号中数字的最短长度Z。

输入描述

一行两个非负整数X和Y，代表字母单个字母空间总数。

0 <= X <= 2^50 - 1

0 < Y <= 5

输出描述

输出新工号中数字部分的最短长度。

示例1

输入：
260 1输出：
1

示例2

输入：
26 1输出：
1说明：
数字长度不能为0

题解

这道题的目的是在给定新工号分配的员工数量 X 和字母长度 Y 的情况下，求出数字部分的最短长度 Z。

解题思路

1. 字母部分的组合数量: 由于字母只能是小写英文字母（a-z），总共有26个字母，因此字母部分的总数可以表示为 $26^Y$。
2. 数字部分的组合数量: 数字部分可以由任意位数的数字组成，且数字部分可以有前导0，因此对于Z位数字，总共有 $10^Z$ 种组合。
3. 目标: 总的工号数应该满足能分配给至少 X 个员工，所以要找出一个最小的 Z，使得字母部分和数字部分的组合数量 $26^Y\times 10^Z$ 不小于 X。
4. 二分查找: 我们可以用二分法来快速找到数字部分的最小长度 Z。初始的搜索区间为 [0, 20]，然后逐步缩小区间，通过判断 $26^Y\times 10^Z$ 是否大于等于 X 来更新搜索区间。

时间复杂度

二分查找的时间复杂度为 O(log⁡Z)，由于最大搜索区间为20，因此时间复杂度接近常数时间。

Java

import java.util.Scanner;
/*** @author code5bug*/
public class Main {public static boolean ok(long x, int y, int z) {// 判断26^y * 10^z 是否大于等于 Xreturn Math.pow(26, y) * Math.pow(10, z) >= x;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long x = scanner.nextLong();int y = scanner.nextInt();int left = 0, right = 20;while (left + 1 < right) {int mid = (left + right) / 2;if (ok(x, y, mid)) {right = mid;} else {left = mid;}}System.out.println(right);}
}

Python

import mathdef ok(x, y, z):# 判断26^y * 10^z 是否大于等于 Xreturn math.pow(26, y) * math.pow(10, z) >= xdef main():x, y = map(int, input().split())left, right = 0, 20while left + 1 < right:mid = (left + right) // 2if ok(x, y, mid):right = midelse:left = midprint(right)if __name__ == "__main__":main()

C++

#include <bits/stdc++.h>
using namespace std;bool ok(long long x, int y, int z)
{// 判断26^y * 10^z 是否大于等于 Xreturn pow(26, y) * pow(10, z) >= x;
}int main()
{long long x;int       y;cin >> x >> y;int left = 0, right = 20;while (left + 1 < right) {int mid = (left + right) / 2;if (ok(x, y, mid)) {right = mid;} else {left = mid;}}cout << right << endl;
}

希望这个专栏不仅能帮您成功通过华为机试，还能让您熟练掌握算法。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏