最新华为OD机试真题-LYA的生日派对座位安排(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM金牌🏅️| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎 在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🪙 LYA的生日派对座位安排
题目描述
LYA要举办一场生日派对,邀请了 位朋友。派对场地里有一排共
个座位,编号从
到
。
要求客人依次入场,并且可以在任何时候离场。
满足以下条件:
- 当一位客人进入时,他会选择一个与其他人距离最远的座位(即最大化他与其他人的距离)。
- 如果有多个这样的座位,他会选择编号最小的座位。
输入格式
第一行包含一个正整数 ,表示派对座位总数。
。
第二行包含一个数组 ,表示客人的进出顺序。
- 若元素值为
,表示一位客人进场。
- 若元素值为负数,如
,表示坐在位置
的客人离场(保证该座位上有客人)。
- 特殊地,位置
的客人不会离开。
输出格式
输出一个整数,表示最后进场的客人将坐在哪个位置。如果所有座位都已被占满,则输出 。
样例输入
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);
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
最新华为OD机试-E+D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测