返回目录

题目描述

疫情期间需要大家保证一定的社交距离，公司组织开交流会议。座位一排共 N 个座位，编号分别为[0,N-1],

要求员工一个接着一个进入会议室，并且可以在任何时候离开会议室。

满足：

• 每当一个员工进入时，需要坐到最大社交距离（最大化自己和其他人的距离的座位）；
• 如果有多个这样的座位，则坐到索引最小的那个座位。

输入描述

会议室座位总数 seatNum

• 1 ≤ seatNum ≤ 500

员工的进出顺序 seatOrLeave 数组

• 元素值为 1，表示进场
• 元素值为负数，表示出场（特殊：位置 0 的员工不会离开）
  例如 -4 表示坐在位置 4 的员工离开（保证有员工坐在该座位上）

输出描述

最后进来员工，他会坐在第几个位置，如果位置已满，则输出-1。

示例：

解题思路

动态维护一个已占用座位的列表，并在每次有员工进入时计算最佳座位，以及在有员工离开时更新座位状态 。

1. 初始化座位状态：使用一个动态数组 seat来记录当前已被占用的座位编号。

2. 处理每个操作：遍历给定的操作序列 seatOrLeave，对于每个操作：

   • 如果操作为正数（即 1），表示有员工进入：

     1. 会议室为空：如果当前 seat数组为空，说明会议室内没有人，新员工直接坐在 0号座位。
     2. 会议室不为空：遍历 seat数组，计算每两个相邻已占座位之间的距离，以及第一个座位到 0号座位的距离和最后一个座位到 seatNum-1的距离。找到这些距离中的最大值对应的座位，作为新员工的座位。
   • 如果操作为负数，表示有员工离开，根据操作值的绝对值找到对应的座位编号，并从 seat数组中移除该座位编号。
3. 更新座位状态：对于进入的员工，将其座位编号添加到 seat数组中，并对 seat数组进行排序，以便下次操作时能快速找到最佳座位。
4. 输出结果：在处理完所有操作后，输出最后一个进入的员工的座位编号。如果会议室已满，则输出 -1。

Python算法源码

# 寻找最佳座位的函数
def find_best_seat(occupied_seats, seat_num):
    # 如果还没有人坐，第一个人坐在0号座位
    if not occupied_seats:
        return 0
    # 如果只有一个人坐，那么下一个人坐在最后一个座位
    if len(occupied_seats) == 1:
        return seat_num - 1

    max_distance = 0
    best_seat = -1
    # 检查是否可以在第一个座位坐下（即第一个座位之前的空位）
    if occupied_seats[0] > 0:
        max_distance = occupied_seats[0]
        best_seat = 0
    # 检查是否可以在最后一个座位坐下（即最后一个座位之后的空位）
    if seat_num - 1 - occupied_seats[-1] > max_distance:
        max_distance = seat_num - 1 - occupied_seats[-1]
        best_seat = seat_num - 1
    # 检查中间的最大间隔，寻找最佳座位
    for i in range(1, len(occupied_seats)):
        distance = (occupied_seats[i] - occupied_seats[i - 1]) // 2
        if distance > max_distance:
            max_distance = distance
            best_seat = occupied_seats[i - 1] + distance
    # 返回最佳座位编号
    return best_seat

def main():
    # 会议室座位总数
    seat_num = int(input())

    # 存放员工进出顺序的字符串
    input_str = input()

    # 处理输入字符串，将其转换为int列表
    seat_or_leave = list(map(int, input_str[1:-1].split(',')))

    occupied_seats = []  # 存储已占用座位的列表
    last_seat = -1  # 存储最后一个坐下的员工的座位号

    # 遍历员工的进出操作
    for action in seat_or_leave:
        if action == 1:  # 进场操作
            best_seat = find_best_seat(occupied_seats, seat_num)
            if best_seat != -1:  # 如果找到了最佳座位
                occupied_seats.append(best_seat)  # 更新已占用座位列表
                occupied_seats.sort()  # 保持座位列表排序
                last_seat = best_seat  # 更新最后一个坐下的座位号
        elif action < 0:  # 出场操作
            action = -action  # 转为正数，表示座位号
            if action in occupied_seats:
                occupied_seats.remove(action)  # 从已占用座位中移除

    print(last_seat)  # 输出最后一个进来员工的座位号

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 500 // 定义最大座位数

// 比较函数，用于排序
int cmp(const void *x, const void *y) {
    return *((int *) x) - *((int *) y);
}

// 定义座位管理类
typedef struct {
    int seat[MAX_SIZE]; // 存储已有人的座位号
    int seat_size; // 已有人的座位号数组的当前大小
    int lastSeatIdx; // 最后一个坐下的座位号
} SeatManager;

// 初始化座位管理类
SeatManager *initSeatManager() {
    SeatManager *manager = (SeatManager *) malloc(sizeof(SeatManager));
    manager->seat_size = 0;
    manager->lastSeatIdx = -1;
    return manager;
}

// 释放座位管理类的内存
void freeSeatManager(SeatManager *manager) {
    free(manager);
}

// 寻找最佳座位
int findBestSeat(SeatManager *manager, int seatNum) {
    int maxDist = -1; // 最大距离
    int bestSeat = -1; // 最佳座位

    // 检查第一个座位是否空闲
    if (manager->seat[0] > 0) {
        maxDist = manager->seat[0];
        bestSeat = 0;
    }

    // 遍历已坐座位，寻找最佳座位
    for (int j = 1; j < manager->seat_size; j++) {
        int dist = (manager->seat[j] - manager->seat[j - 1]) / 2; // 计算距离
        if (dist > maxDist) {
            maxDist = dist;
            bestSeat = manager->seat[j - 1] + dist;
        }
    }

    // 检查最后一个座位是否空闲
    if (seatNum - 1 - manager->seat[manager->seat_size - 1] > maxDist) {
        bestSeat = seatNum - 1;
    }

    return bestSeat;
}

int main() {
    int seatNum; // 座位总数
    scanf("%d", &seatNum); // 读取座位总数

    getchar(); // 读取换行符

    int seatOrLeave[MAX_SIZE] = {0}; // 存储进出座位的数组
    int seatOrLeave_size = 0; // 进出座位数组的当前大小

    // 读取进出座位的序列，支持两种格式：[数字,] 或 数字,
    while (scanf("[%d", &seatOrLeave[seatOrLeave_size]) || scanf("%d", &seatOrLeave[seatOrLeave_size])) {
        seatOrLeave_size++; // 数组大小增加
        if (getchar() != ',') break; // 如果不是逗号，则停止读取
    }

    SeatManager *manager = initSeatManager(); // 初始化座位管理类

    // 遍历所有进出记录
    int i = 0;
    while (i < seatOrLeave_size) {
        int info = seatOrLeave[i]; // 当前记录

        // 如果是负数，表示有人离开
        if (info < 0) {
            int leaveIdx = -info; // 离开的座位号
            for (int j = 0; j < manager->seat_size; j++) {
                if (manager->seat[j] == leaveIdx) {
                    // 移除离开的座位号
                    for (int k = j; k < manager->seat_size - 1; k++) {
                        manager->seat[k] = manager->seat[k + 1];
                    }
                    manager->seat_size--; // 座位数组大小减小
                    break;
                }
            }
        } else {
            // 如果是第一个人，则坐在第一个位置
            if (manager->seat_size == 0) {
                manager->lastSeatIdx = 0;
                manager->seat[manager->seat_size++] = manager->lastSeatIdx;
            } else {
                int bestSeat = findBestSeat(manager, seatNum); // 寻找最佳座位

                // 如果找到了最佳座位，将其加入数组
                if (bestSeat >= 0 && manager->seat_size < seatNum) {
                    manager->seat[manager->seat_size++] = bestSeat;
                    qsort(manager->seat, manager->seat_size, sizeof(int), cmp); // 排序座位数组
                }

                manager->lastSeatIdx = bestSeat; // 更新最后一个坐下的座位号
            }
        }
        i++;
    }

    printf("%d\n", manager->lastSeatIdx); // 打印最后一个坐下的座位号

    freeSeatManager(manager); // 释放座位管理类的内存

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
  
    // 主要逻辑函数，计算最后一个入座的座位索引
    static int solution(int seatNum, ArrayList<Integer> seatOrLeave) {
        ArrayList<Integer> seatIdx = new ArrayList<>(); // 记录当前已入座的座位索引
        int lastSeatIdx = -1; // 记录最后一个入座的座位索引，默认为-1表示无人入座
      
        for (int info : seatOrLeave) {
            if (info < 0) { // 如果info小于0，表示有人离开
                int leaveIdx = -info; // 离开的座位索引
                seatIdx.remove((Integer)leaveIdx); // 从已入座座位列表中移除离开的座位索引
                continue;
            }
          
            if (seatIdx.size() == seatNum) { // 如果所有座位已满
                lastSeatIdx = -1; // 设置最后一个入座的座位索引为-1
                continue;
            }
          
            if (seatIdx.isEmpty()) { // 如果没有座位被占据
                seatIdx.add(0); // 将第一个座位入座
                lastSeatIdx = 0; // 更新最后一个入座的座位索引
            } else if (seatIdx.size() == 1) { // 如果只有一个座位被占据
                seatIdx.add(seatNum - 1); // 将最后一个座位入座
                lastSeatIdx = seatNum - 1; // 更新最后一个入座的座位索引
            } else { // 如果有多个座位被占据
                int bestSeatIdx = -1; // 最佳座位索引
                int bestSeatDis = -1; // 最佳座位与相邻座位的间距
              
                int left = seatIdx.get(0); // 左侧相邻座位索引
                for (int i = 1; i < seatIdx.size(); i++) {
                    int right = seatIdx.get(i); // 右侧相邻座位索引
                    int dis = right - left - 1; // 计算两个相邻座位之间的间距
                  
                    if (dis > 0) { // 如果间距大于0，表示之间有空座
                        int curSeatDis = dis / 2 - (dis % 2 == 0 ? 1 : 0); // 计算当前座位与相邻座位的中间位置
                        int curSeatIdx = left + curSeatDis + 1; // 计算当前最佳座位索引
                      
                        if (curSeatDis > bestSeatDis) { // 如果当前座位间距比最佳座位间距大
                            bestSeatDis = curSeatDis; // 更新最佳座位间距
                            bestSeatIdx = curSeatIdx; // 更新最佳座位索引
                        }
                    }
                  
                    left = right; // 更新左侧相邻座位索引
                }
              
                if (seatIdx.get(seatIdx.size() - 1) < seatNum - 1) { // 如果最后一个座位索引小于座位总数减1
                    int curSeatDis = seatNum - 1 - seatIdx.get(seatIdx.size() - 1) - 1; // 计算最后一个座位到末尾的间距
                    int curSeatIdx = seatNum - 1; // 最后一个座位索引
                  
                    if (curSeatDis > bestSeatDis) { // 如果当前座位间距比最佳座位间距大
                        bestSeatIdx = curSeatIdx; // 更新最佳座位索引
                    }
                }
              
                if (bestSeatIdx > 0) { // 如果存在最佳座位索引
                    seatIdx.add(bestSeatIdx); // 将最佳座位索引加入已入座座位列表
                    Collections.sort(seatIdx); // 对已入座座位列表进行排序
                }
              
                lastSeatIdx = bestSeatIdx; // 更新最后一个入座的座位索引
            }
        }
      
        return lastSeatIdx; // 返回最后一个入座的座位索引
    }
  
    // 主函数，从控制台输入座位数和座位状态，并输出最后一个入座的座位索引
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int seatNum = scanner.nextInt(); // 输入座位数
      
        scanner.nextLine(); // 读取换行符
        String s = scanner.nextLine(); // 输入座位状态
      
        // 处理输入的座位状态字符串，将逗号和方括号替换为空格
        s = s.replace(",", " ").replace("[", " ").replace("]", " ");
      
        ArrayList<Integer> seatOrLeave = new ArrayList<>(); // 存储座位状态的列表
        Scanner tokenizer = new Scanner(s); // 创建扫描器
      
        while (tokenizer.hasNext()) { // 遍历扫描器中的每个元素
            String token = tokenizer.next(); // 获取下一个元素
            seatOrLeave.add(Integer.parseInt(token)); // 将元素转换为整数并添加到座位状态列表中
        }
      
        System.out.println(solution(seatNum, seatOrLeave)); // 输出最后一个入座的座位索引
      
        scanner.close(); // 关闭输入流
        tokenizer.close(); // 关闭扫描器
    }
}