华为OD机试算法： 最大社交距离
题目描述
疫情期间需要大家保证一定的社交距离，公司组织开交流会议。
座位一排共 N 个座位，编号分别为 [0, N - 1] 。
要求员工一个接着一个进入会议室，并且可以在任何时候离开会议室。
满足：
每当一个员工进入时，需要坐到最大社交距离（最大化自己和其他人的距离的座位）；
如果有多个这样的座位，则坐到索引最小的那个座位
输入描述
会议室座位总数 seatNum
1 ≤ seatNum ≤ 500
员工的进出顺序 seatOrLeave 数组
元素值为 1，表示进场
元素值为负数，表示出场（特殊：位置 0 的员工不会离开）
例如 -4 表示坐在位置 4 的员工离开（保证有员工坐在该座位上）
输出描述
最后进来员工，他会坐在第几个位置，如果位置已满，则输出-1。
用例
题目解析
1.首先，我们需要创建一个长度为seatNum的数组seats，用于记录每个座位的状态，初始值为0表示空座位，1表示有人坐在该座位上。
2.然后，遍历seatOrLeave数组，对于每个元素：
·如果元素值为1，表示员工进场，需要找到最大社交距离的座位。我们可以从左到右遍历seats数组，找到第一个值为0的元素，将其值设为1，表示有人坐在该座位上。如果找不到这样的座位，说明座位已满，返回-1。
·如果元素值为负数，表示员工离开，将对应位置的座位状态设为0，表示该座位变为空座位。
3.最后，返回最后一个进入的员工坐在的位置。
const rl = require("readline").createInterface({ input: process.stdin });
const readline = async () => (await rl[Symbol.asyncIterator]().next()).value;
(async function () {
const seatNum = parseInt(await readline());
const seatOrLeave = JSON.parse(await readline());
console.log(getResult(seatNum, seatOrLeave));
})();
function getResult(seatNum, seatOrLeave) {
let seatIdx = [];
let lastSeatIdx = -1;
for (let info of seatOrLeave) {
if (info < 0) {
const leaveIdx = -info;
seatIdx = seatIdx.filter((idx) => idx != leaveIdx);
} else {
if (seatIdx.length === seatNum) continue;
if (seatIdx.length === 0) {
seatIdx.push(0);
lastSeatIdx = 0;
} else if (seatIdx.length === 1) {
seatIdx.push(seatNum - 1);
lastSeatIdx = seatNum - 1;
} else {
let bestSeatIdx = -1;
let bestSeatDis = -1;
let left = seatIdx[0];
for (let i = 1; i < seatIdx.length; i++) {
const right = seatIdx[i];
const dis = right - left - 1;
if (dis > 0) {
const curSeatDis = Math.floor(dis / 2) - (dis % 2 === 0 ? 1 : 0);
const curSeatIdx = left + curSeatDis + 1;
if (curSeatDis > bestSeatDis) {
bestSeatDis = curSeatDis;
bestSeatIdx = curSeatIdx;
}
}
left = right;
}
if (seatIdx.at(-1) < seatNum - 1) {
const curSeatDis = seatNum - 1 - seatIdx.at(-1) - 1;
const curSeatIdx = seatNum - 1;
if (curSeatDis > bestSeatDis) {
bestSeatIdx = curSeatIdx;
}
}
if (bestSeatIdx > 0) {
seatIdx.push(bestSeatIdx);
seatIdx.sort((a, b) => a - b);
}
lastSeatIdx = bestSeatIdx;
}
}
}
return lastSeatIdx;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int seatNum = Integer.parseInt(sc.nextLine());
String tmp = sc.nextLine();
int[] seatOrLeave =
Arrays.stream(tmp.substring(1, tmp.length() - 1).split(", "))
.mapToInt(Integer::parseInt)
.toArray();
System.out.println(getResult(seatNum, seatOrLeave));
}
public static int getResult(int seatNum, int[] seatOrLeave) {
ArrayList<Integer> seatIdx = new ArrayList<>();
int lastSeatIdx = -1;
for (int info : seatOrLeave) {
if (info < 0) {
int leaveIdx = -info;
seatIdx.remove(new Integer(leaveIdx));
continue;
}
if (seatIdx.size() == seatNum) {
lastSeatIdx = -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) {
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) {
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);
seatIdx.sort((a, b) -> a - b);
}
lastSeatIdx = bestSeatIdx;
}
}
return lastSeatIdx;
}
}
seatNum = int(input())
seatOrLeave = eval(input())
def getResult():
seatIdx = []
lastSeatIdx = -1
for info in seatOrLeave:
if info < 0:
leaveIdx = -info
seatIdx.remove(leaveIdx)
continue
if len(seatIdx) == seatNum:
lastSeatIdx = -1
continue
if len(seatIdx) == 0:
seatIdx.append(0)
lastSeatIdx = 0
elif len(seatIdx) == 1:
seatIdx.append(seatNum - 1)
lastSeatIdx = seatNum - 1
else:
bestSeatIdx = -1
bestSeatDis = -1
left = seatIdx[0]
for i in range(1, len(seatIdx)):
right = seatIdx[i]
dis = right - left - 1
if dis > 0:
curSeatDis = dis // 2 - (1 if dis % 2 == 0 else 0)
curSeatIdx = left + curSeatDis + 1
if curSeatDis > bestSeatDis:
bestSeatDis = curSeatDis
bestSeatIdx = curSeatIdx
left = right
if seatIdx[-1] < seatNum - 1:
curSeatDis = seatNum - 1 - seatIdx[-1] - 1
curSeatIdx = seatNum - 1
if curSeatDis > bestSeatDis:
bestSeatIdx = curSeatIdx
if bestSeatIdx > 0:
seatIdx.append(bestSeatIdx)
seatIdx.sort()
lastSeatIdx = bestSeatIdx
return lastSeatIdx
print(getResult())
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 500
int cmp(const void *a, const void *b) {
return *((int *) a) - *((int *) b);
}
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;
}
int seatIdx[MAX_SIZE];
int seatIdx_size = 0;
int lastSeatIdx = -1;
for (int i = 0; i < seatOrLeave_size; i++) {
int info = seatOrLeave[i];
if (info < 0) {
int leaveIdx = -info;
for (int j = 0; j < seatIdx_size; j++) {
if (seatIdx[j] == leaveIdx) {
for (int k = j; k < seatIdx_size - 1; k++) {
seatIdx[k] = seatIdx[k + 1];
}
seatIdx_size--;
break;
}
}
continue;
}
if (seatIdx_size == seatNum) {
lastSeatIdx = -1;
continue;
}
if (seatIdx_size == 0) {
seatIdx[seatIdx_size++] = 0;
lastSeatIdx = 0;
} else if (seatIdx_size == 1) {
seatIdx[seatIdx_size++] = seatNum - 1;
lastSeatIdx = seatNum - 1;
} else {
int bestSeatIdx = -1;
int bestSeatDis = -1;
int left = seatIdx[0];
for (int j = 1; j < seatIdx_size; j++) {
int right = seatIdx[j];
int dis = right - left - 1;
if (dis > 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[seatIdx_size - 1] < seatNum - 1) {
int curSeatDis = seatNum - 1 - seatIdx[seatIdx_size - 1] - 1;
int curSeatIdx = seatNum - 1;
if (curSeatDis > bestSeatDis) {
bestSeatIdx = curSeatIdx;
}
}
if (bestSeatIdx > 0) {
seatIdx[seatIdx_size++] = bestSeatIdx;
qsort(seatIdx, seatIdx_size, sizeof(int), cmp);
}
lastSeatIdx = bestSeatIdx;
}
}
printf("%d\n", lastSeatIdx);
return 0;
}
查看1道真题和解析
投递华为等公司10个岗位 >
华为泡池子881人在聊