最新华为OD机试真题-卢小姐的排队问题(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 卢小姐的排队问题(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

💽 卢小姐的排队问题

问题描述

LYA 的班级要进行一次班级活动，全班同学按照学号从小到大排成一列。但是卢小姐来晚了，没有来得及排队。现在卢小姐想知道，她应该插入到队列的哪个位置，才能保证队列仍然是按照学号从小到大排列的。请你帮助卢小姐找到她应该插入的位置。

输入格式

第一行输入一个整数 ，表示已经排好队的同学人数。

第二行输入 个整数，表示已经排好队的同学的学号，以空格分隔。

第三行输入一个整数 ，表示卢小姐的学号。

输出格式

输出一个整数，表示卢小姐应该插入的位置（从 开始编号）。

样例输入

7
93 95 97 100 102 123 155
110

样例输出

6

数据范围

• 
• 学号为不超过 的正整数。

题解

本题可以使用二分查找的方法来解决。可以将已经排好队的同学的学号看作一个有序数组，然后在这个有序数组中二分查找卢小姐的学号应该插入的位置。

具体步骤如下：

1. 将左指针 初始化为 ，右指针 初始化为 。
2. 当 时，计算中点 。
3. 如果卢小姐的学号小于 ，则将右指针 更新为 ；否则将左指针 更新为 。
4. 重复步骤 2-3，直到 。
5. 最后， 即为卢小姐应该插入的位置。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

nums = list(map(int, input().split()))
target = int(input())
n = len(nums)

left, right = 0, n
while left < right:
    mid = (left + right) // 2
    if target < nums[mid]:
        right = mid
    else:
        left = mid + 1

print(left + 1)

• Java

import java.util.Scanner;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        ArrayList<Integer> nums = new ArrayList<>();
        while (tokenizer.hasMoreTokens()) {
            nums.add(Integer.parseInt(tokenizer.nextToken()));
        }

        int target = scanner.nextInt();
        int n = nums.size();

        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target < nums.get(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(left + 1);
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> nums;
    int num;
    while (iss >> num) {
        nums.push_back(num);
    }

    int target;
    cin >> target;
    int n = nums.size();

    int left = 0, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (target < nums[mid]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << left + 1 << endl;
    return 0;
}