工号不够用了怎么办？ - 华为OD统一考试(E卷)

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个字母，因此字母部分的总数可以表示为 。
2. 数字部分的组合数量: 数字部分可以由任意位数的数字组成，且数字部分可以有前导0，因此对于Z位数字，总共有 种组合。
3. 目标: 总的工号数应该满足能分配给至少 X 个员工，所以要找出一个最小的 Z，使得字母部分和数字部分的组合数量 不小于 X。
4. 二分查找: 我们可以用二分法来快速找到数字部分的最小长度 Z。初始的搜索区间为 [0, 20]，然后逐步缩小区间，通过判断 是否大于等于 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 是否大于等于 X
        return Math.pow(26, y) * Math.pow(10, z) >= x;