刷题笔记合集🔗

最大社交距离

问题描述

在疫情期间，为了保证社交距离，公司组织了一场特殊的交流会议。会议室有一排共 个座位，编号从 到 。员工们需要按照以下规则进入并就座：

1. 每位员工进入时，必须选择能够最大化社交距离的座位（即与其他已就座员工距离最远的位置）。
2. 如果存在多个满足条件的座位，员工应选择编号最小的那个。
3. 员工可以在任何时候离开会议室。
4. 特别注意，坐在 0 号位置的员工不会离开。

你的任务是确定最后一位进入会议室的员工将会坐在哪个位置。

输入格式

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

第二行是一个整数数组 ，表示员工的进出顺序。数组中的元素含义如下：

• 1 表示一名员工进入会议室
• 负数 表示坐在 号位置的员工离开（保证该位置确实有人）

输出格式

输出一个整数，表示最后进入的员工所坐的位置编号。如果所有座位都已被占用，则输出 -1。

样例输入1

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

样例输出1

5

样例输入2

5
[1, 1, 1, 1, 1, 1]

样例输出2

-1

样例解释

数据范围

• 
• 数组长度不超过 500

题解

双指针+模拟

算法思路

1. 数据结构：

   • 使用一个数组 vis 来记录每个座位的占用状态。
   • 使用一个变量 ans 来记录最后一个进入的人的座位。

2. 处理新人进入：

   • 如果是第一个人，直接坐在第一个位置（索引1）。
   • 否则，遍历所有座位，找到能够最大化社交距离的位置。
   • 使用双指针技巧：lmaxv 记录左边最近的已占用座位，rmaxv 记录右边最近的已占用座位。

3. 寻找最佳座位：

   • 对于每个未占用的座位，计算它到左右两边最近已占用座位的距离。
   • 取这两个距离的较小值作为该座位的社交距离。
   • 更新全局最大社交距离和对应的座位索引。

4. 处理人员离开：

   • 直接将对应座位的状态标记为未占用。

5. 特殊情况处理：

   • 如果所有座位都已被占用，新人无法就座，返回-1。
   • 确保不会移除0号位置的人。

时间复杂度分析

• 对于每个事件（进入或离开），我们最坏情况下需要遍历所有座位一次。
• 总时间复杂度：O(n * m)，其中 n 是座位数，m 是事件数。

空间复杂度分析

• 我们使用了一个长度为 n+1 的数组来记录座位状态。
• 空间复杂度：O(n)

代码实现的关键点

1. 使用 vis 数组快速判断座位是否被占用。
2. 使用双指针 lmaxv 和 rmaxv 来高效计算社交距离。
3. 特别处理第一个人和只有一个人的情况，以简化逻辑。
4. 注意座位编号从0开始，但我们的实现从1开始，最后返回结果时需要减1。

参考代码

• Python

def getResult(n, a):
    # 初始化座位占用状态数组，索引0不使用，所以长度为n+1
    vis = [0] * (n + 1)
    # 记录最后一个进入的人的座位
    ans = 0
    
    for val in a:
        if val == 1:  # 有新人进入
            lmaxv = 0  # 左边最近的已占用座位
            maxv = 0   # 当前最大社交距离
            idx = 1    # 当前选择的座位索引
            
            # 如果是第一个人，直接坐在第一个位置
            if vis.count(1) == 0:
                vis[idx] = 1
                ans = idx
                continue
            
            rmaxv = 0  # 右边最近的已占用座位
            
            # 遍历所有座位，寻找最大社交距离的位置
            for i in range(1, n + 1):
                if vis[i] == 0:  # 当前座位未被占用
                    ldist = i - lmaxv  # 到左边最近已占用座位的距离
                    rdist = rmaxv - i  # 到右边最近已占用座位的距离
                    if rmaxv == n + 1:  # 如果右边没有已占用的座位
                        rdist = n * 10  # 将右距离设置为一个很大的值
                    dist = min(ldist, rdist)  # 取左右距离的较小值作为社交距离
                    if dist > maxv:  # 更新最大社交距离和对应的座位
                        maxv, idx = dist, i
                else:  # 当前座位已被占用
                    lmaxv = i  # 更新左边最近的已占用座位
                    rmaxv = lmaxv + 1
                    while rmaxv <= n and vis[rmaxv] == 0:
                        rmaxv += 1  # 寻找右边最近的已占用座位
            
            # 选定座位，更新状态
            vis[idx] = 1
            ans = idx
        else:  # 有人离开
            vis[-val + 1] = 0  # 将对应座位标记为未占用
    
    return ans - 1  # 返回最后一个进入的人的座位号（减1是因为题目座位从0开始编号）

# 输入处理
n = int(input())  # 读取座位总数
a = eval(input())  # 读取事件序列

# 输出结果
print(getResult(n, a))

• C

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

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int getResult(int n, int* a, int aSize) {
    // 初始化座位占用状态数组，索引0不使用，所以长度为n+1
    int* vis = (int*)calloc(n + 1, sizeof(int));
    int ans = 0;  // 记录最后一个进入的人的座位
    
    for (int i = 0; i < aSize; i++) {
        int val = a[i];
        if (val == 1) {  // 有新人进入
            int lmaxv = 0;  // 左边最近的已占用座位
            int maxv = 0;   // 当前最大社交距离
            int idx = 1;    // 当前选择的座位索引
            
            // 检查是否是第一个人
            int firstPerson = 1;
            for (int j = 1; j <= n; j++) {
                if (vis[j] == 1) {
                    firstPerson = 0;
                    break;
                }
            }
            
            // 如果是第一个人，直接坐在第一个位置
            if (firstPerson) {
                vis[idx] = 1;
                ans = idx;
                continue;
            }
            
            int rmaxv = 0;  // 右边最近的已占用座位
            
            // 遍历所有座位，寻找最大社交距离的位置
            for (int i = 1; i <= n; i++) {
                if (vis[i] == 0) {  // 当前座位未被占用
                    int ldist = i - lmaxv;  // 到左边最近已占用座位的距离
                    int rdist = rmaxv - i;  // 到右边最近已占用座位的距离
                    if (rmaxv == n + 1) rdist = n * 10;  // 如果右边没有已占用的座位，将右距离设置为一个很大的值
                    int dist = MIN(ldist, rdist);  // 取左右距离的较小值作为社交距离
                    if (dist > maxv) {  // 更新最大社交距离和对应的座位
                        maxv = dist;
                        idx = i;
                    }
                } else {  // 当前座位已被占用
                    lmaxv = i;  // 更新左边最近的已占用座位
                    rmaxv = lmaxv + 1;
                    while (rmaxv <= n && vis[rmaxv] == 0) rmaxv++;  // 寻找右边最近的已占用座位
                }
            }
            
            // 选定座位，更新状态
            vis[idx] = 1;
            ans = idx;
        } else {  // 有人离开
            vis[-val + 1] = 0;  // 将对应座位标记为未占用
        }
    }
    
    free(vis);  // 释放动态分配的内存
    return ans - 1;  // 返回最后一个进入的人的座位号（减1是因为题目座位从0开始编号）
}

int main() {
    int n;
    scanf("%d", &n);  // 读