最新华为OD机试真题-LYA的生日派对座位安排(200分)

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

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

💻 ACM金牌🏅️| 多次AK大厂笔试 ｜ 编程一对一辅导

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

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎 在线评测链接

LYA的生日派对座位安排(200分)

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

🍓OJ题目截图

🪙 LYA的生日派对座位安排

题目描述

LYA要举办一场生日派对，邀请了 位朋友。派对场地里有一排共 个座位，编号从 到 。

要求客人依次入场，并且可以在任何时候离场。

满足以下条件：

1. 当一位客人进入时，他会选择一个与其他人距离最远的座位（即最大化他与其他人的距离）。
2. 如果有多个这样的座位，他会选择编号最小的座位。

输入格式

第一行包含一个正整数 ，表示派对座位总数。。

第二行包含一个数组 ，表示客人的进出顺序。

• 若元素值为 ，表示一位客人进场。
• 若元素值为负数，如 ，表示坐在位置 的客人离场（保证该座位上有客人）。
• 特殊地，位置 的客人不会离开。

输出格式

输出一个整数，表示最后进场的客人将坐在哪个位置。如果所有座位都已被占满，则输出 。

样例输入

10
[1,1,1,1,-4,1]

样例输出

5

样例解释

• 第一位客人选择座位 。
• 第二位客人选择座位 ，与第一位客人距离最远。
• 第三位客人选择座位 ，最大化与其他人的距离。
• 第四位客人选择座位 。
• 坐在座位 的客人离场。
• 第五位客人选择座位 。

数据范围

题解

为了实现这个问题，我们需要跟踪每个座位的状态（是否被占用），并在每次有客人进场时找到可以使社交距离最大的座位。可以使用一个列表来记录已经被占用的座位，并通过遍历找到最佳座位。对于离场操作，只需从列表中移除相应的座位即可。

参考代码

• Python

def find_seat(seat_count, actions):
    occupied = []
    last_seat = -1

    for action in actions:
        if action < 0:
            occupied.remove(-action)
        else:
            if len(occupied) == seat_count:
                last_seat = -1
            elif not occupied:
                occupied.append(0)
                last_seat = 0
            elif len(occupied) == 1:
                occupied.append(seat_count - 1)
                last_seat = seat_count - 1
            else:
                best_dist = -1
                best_seat = -1

                if occupied[0] != 0:
                    best_dist = occupied[0]
                    best_seat = 0

                for i in range(1, len(occupied)):
                    prev = occupied[i - 1]
                    curr = occupied[i]
                    dist = (curr - prev) // 2
                    if dist > best_dist:
                        best_dist = dist
                        best_seat = prev + dist

                if seat_count - 1 not in occupied and seat_count - 1 - occupied[-1] > best_dist:
                    best_seat = seat_count - 1

                occupied.append(best_seat)
                occupied.sort()
                last_seat = best_seat

    return last_seat

# 输入获取
seat_num = int(input())
actions = eval(input())

# 输出结果
print(find_seat(seat_num, actions))

• Java

import java.util.*;

public class Main {
    public static int findSeat(int seatCount, List<Integer> actions) {
        List<Integer> occupied = new ArrayList<>();
        int lastSeat = -1;

        for (int action : actions) {
            if (action < 0) {
                occupied.remove(Integer.valueOf(-action));
            } else {
                if (occupied.size() == seatCount) {
                    lastSeat = -1;
                } else if (occupied.isEmpty()) {
                    occupied.add(0);