E-最大社交距离(100p)
刷题笔记合集🔗
最大社交距离
问题描述
在疫情期间，为了保证社交距离，公司组织了一场特殊的交流会议。会议室有一排共 个座位，编号从
到
。员工们需要按照以下规则进入并就座：
- 每位员工进入时，必须选择能够最大化社交距离的座位（即与其他已就座员工距离最远的位置）。
- 如果存在多个满足条件的座位，员工应选择编号最小的那个。
- 员工可以在任何时候离开会议室。
- 特别注意，坐在 0 号位置的员工不会离开。
你的任务是确定最后一位进入会议室的员工将会坐在哪个位置。
输入格式
第一行包含一个整数 ，表示座位总数。
第二行是一个整数数组 ，表示员工的进出顺序。数组中的元素含义如下：
- 1 表示一名员工进入会议室
- 负数
表示坐在
号位置的员工离开（保证该位置确实有人）
输出格式
输出一个整数，表示最后进入的员工所坐的位置编号。如果所有座位都已被占用，则输出 -1。
样例输入1
10
[1, 1, 1, 1, -4, 1]
样例输出1
5
样例输入2
5
[1, 1, 1, 1, 1, 1]
样例输出2
-1
样例解释
| 样例1 | 1. 第一个人进入，坐在 0 号位置 2. 第二个人进入，坐在 9 号位置（最远距离） 3. 第三个人进入，坐在 4 号位置（中间） 4. 第四个人进入，坐在 2 号位置 5. 4 号位置的人离开 6. 最后一个人进入，坐在 5 号位置 |
| 样例2 | 前 5 个人分别坐在 0, 4, 2, 1, 3 号位置 第 6 个人进入时所有座位已满，无法就座 |
数据范围
数组长度不超过 500
题解
双指针+模拟
算法思路
-
数据结构：
- 使用一个数组
vis来记录每个座位的占用状态。 - 使用一个变量
ans来记录最后一个进入的人的座位。
- 使用一个数组
-
处理新人进入：
- 如果是第一个人，直接坐在第一个位置（索引1）。
- 否则，遍历所有座位，找到能够最大化社交距离的位置。
- 使用双指针技巧：
lmaxv记录左边最近的已占用座位，rmaxv记录右边最近的已占用座位。
-
寻找最佳座位：
- 对于每个未占用的座位，计算它到左右两边最近已占用座位的距离。
- 取这两个距离的较小值作为该座位的社交距离。
- 更新全局最大社交距离和对应的座位索引。
-
处理人员离开：
- 直接将对应座位的状态标记为未占用。
-
特殊情况处理：
- 如果所有座位都已被占用，新人无法就座，返回-1。
- 确保不会移除0号位置的人。
时间复杂度分析
- 对于每个事件（进入或离开），我们最坏情况下需要遍历所有座位一次。
- 总时间复杂度：O(n * m)，其中 n 是座位数，m 是事件数。
空间复杂度分析
- 我们使用了一个长度为 n+1 的数组来记录座位状态。
- 空间复杂度：O(n)
代码实现的关键点
- 使用
vis数组快速判断座位是否被占用。 - 使用双指针
lmaxv和rmaxv来高效计算社交距离。 - 特别处理第一个人和只有一个人的情况，以简化逻辑。
- 注意座位编号从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); // 读取座位总数
char input[10000];
scanf(" %[^\n]", input); // 读取整行输入
// 解析输入字符串，提取事件序列
int* a = (int*)malloc(sizeof(int) * 10000);
int aSize = 0;
char* token = strtok(input, "[], ");
while (token != NULL) {
a[aSize++] = atoi(token);
token = strtok(NULL, "[], ");
}
printf("%d\n", getResult(n, a, aSize)); // 输出结果
free(a); // 释放动态分配的内存
return 0;
}
- Javascript
function getResult(n, a) {
// 初始化座位占用状态数组，索引0不使用，所以长度为n+1
let vis = new Array(n + 1).fill(0);
// 记录最后一个进入的人的座位
let ans = 0;
for (let val of a) {
if (val === 1) { // 有新人进入
let lmaxv = 0; // 左边最近的已占用座位
let maxv = 0; // 当前最大社交距离
let idx = 1; // 当前选择的座位索引
// 如果是第一个人，直接坐在第一个位置
if (vis.reduce((a, b) => a + b, 0) === 0) {
vis[idx] = 1;
ans = idx;
continue;
}
let rmaxv = 0; // 右边最近的已占用座位
// 遍历所有座位，寻找最大社交距离的位置
for (let i = 1; i <= n; i++) {
if (vis[i] === 0) { // 当前座位未被占用
let ldist = i - lmaxv; // 到左边最近已占用座位的距离
let rdist = rmaxv - i; // 到右边最近已占用座位的距离
if (rmaxv === n + 1) rdist = n * 10; // 如果右边没有已占用的座位，将右距离设置为一个很大的值
let dist = Math.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; // 将对应座位标记为未占用
}
}
return ans - 1; // 返回最后一个进入的人的座位号（减1是因为题目座位从0开始编号）
}
// 输入处理
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n;
let a;
rl.question('', (answer) => {
n = parseInt(answer); // 读取座位总数
rl.question('', (answer) => {
a = JSON.parse(answer); // 读取事件序列
console.log(getResult(n, a)); // 输出结果
rl.close();
});
});
- Java
import java.util.*;
public class Main {
public static int getResult(int n, int[] a) {
// 初始化座位占用状态数组，索引0不使用，所以长度为n+1
int[] vis = new int[n + 1];
// 记录最后一个进入的人的座位
int ans = 0;
for (int val : a) {
if (val == 1) { // 有新人进入
int lmaxv = 0; // 左边最近的已占用座位
int maxv = 0; // 当前最大社交距离
int idx = 1; // 当前选择的座位索引
// 如果是第一个人，直接坐在第一个位置
if (Arrays.stream(vis).sum() == 0) {
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 = Math.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; // 将对应座位标记为未占用
}
}
return ans - 1; // 返回最后一个进入的人的座位号（减1是因为题目座位从0开始编号）
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取座位总数
scanner.nextLine(); // 消耗换行符
String input = scanner.nextLine(); // 读取事件序列字符串
input = input.substring(1, input.length() - 1); // 去掉首尾的方括号
String[] strArray = input.split(","); // 分割字符串
int[] a = new int[strArray.length];
for (int i = 0; i < strArray.length; i++) {
a[i] = Integer.parseInt(strArray[i].trim()); // 将字符串转换为整数
}
System.out.println(getResult(n, a)); // 输出结果
}
}
- Cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;
int getResult(int n, vector<int>& a) {
// 初始化座位占用状态数组，索引0不使用，所以长度为n+1
vector<int> vis(n + 1, 0);
// 记录最后一个进入的人的座位
int ans = 0;
for (int val : a) {
if (val == 1) { // 有新人进入
int lmaxv = 0; // 左边最近的已占用座位
int maxv = 0; // 当前最大社交距离
int idx = 1; // 当前选择的座位索引
// 如果是第一个人，直接坐在第一个位置
if (count(vis.begin(), vis.end(), 1) == 0) {
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; // 将对应座位标记为未占用
}
}
return ans - 1; // 返回最后一个进入的人的座位号（减1是因为题目座位从0开始编号）
}
int main() {
int n;
cin >> n; // 读取座位总数
string input;
cin.ignore(); // 忽略换行符
getline(cin, input); // 读取整行输入
// 解析输入字符串，提取事件序列
vector<int> a;
stringstream ss(input.substr(1, input.length() - 2)); // 去掉首尾的方括号
string item;
while (getline(ss, item, ',')) {
a.push_back(stoi(item));
}
cout << getResult(n, a) << endl; // 输出结果
return 0;
}