思路：模拟

首先，按顺序考虑数组中的每一个值$w[i]$，同时维护一个数组$person$按从小到大的顺序存储已经就座的这些员工的编号。

• $w[i]<0$，我们需要在$person$数组中找到与$w[i]$相等的数，并删除
• $w[i]=0$，根据题目说明，不予处理
• $w[i]>0$，需要分以下几种情况讨论

情况1：$person$长度为0，说明没有人落座，那么按照题目要求，应该落座在索引0的位置上

情况2：$person$长度为1，说明只有一个人落座，根据情况1可知，这个人一定在索引0的位置上，因此当前这个人应该落座在索引位置为$setNum-1$的位置上

情况3：$person$长度$\ge2$，那么我们应该枚举所有的空位，根据题意去求一个位置，使得这个位置到其他落座的人的最小值最大，那么由于$person$是一个有序数组，因此可以把整个座位分成$k$份，$k$为$person$的长度，比如$person=[0,4,9]$，那么就可以把区间分为$[0,4],[4,9]$这两份，特殊的，其实还是需要考虑$[9,9]$这个区间，但因为这个区间没办法落座，因此不需要考虑

比如对于区间$[a,b]$，那么最优解一定是选择区间$[a,b]$的中间位置$pos$，我们计算其距离最大值为$ceil(\frac{b-a-1}{2})$，$ceil()$表示上取整，例如$[0,9]$区间，距离最大值为$ceil(\frac{9-0-1}{2})=4$，一边枚举一边更新即可，最后将对应的位置$pos$插入之后，需要对$person$数组进行重新排序。

JavaScript

// 引入readline模块
const readline = require('readline');

// 创建readline接口
const rl = readline.createInterface({
  input: process.stdin,  // 从标准输入读取数据
  output: process.stdout  // 输出到标准输出
});

let setNum;  // 座位总数
let w;       // 事件序列

// 读取第一行输入
rl.once('line', (input) => {
  setNum = parseInt(input);

  // 读取第二行输入
  rl.once('line', (input) => {
    // 处理第二行输入，提取座位事件序列
    w = input.slice(1, -1).split(',').map(Number);

    const person = [];  // 已经就座的座位编号
    let ans = -1;       // 输出结果

    // 遍历座位事件序列
    for (const x of w) {
      if (x < 0) {  // 如果为负数，表示有人要离场
        const pos = -x;  // 离场的座位编号
        const idx = person.indexOf(pos);  // 查找座位在已就座序列中的下标

        if (idx !== -1) {
          person.splice(idx, 1);  // 从已就座序列中移除该座位
        }
      } else if (x === 0) {
        continue;  // 如果为零，表示无事件，继续下一次循环
      } else if (person.length === 0) {
        person.push(0);  // 如果座位没有坐人，第一个人坐在最左边
        ans = 0;         // 更新输出结果
      } else if (person.length === 1) {
        person.push(setNum - 1);  // 如果座位上只有一个人，第二个人坐在最右边
        ans = setNum - 1;         // 更新输出结果
      } else {
        let pos = -1;   // 新来的人坐的位置
        let maxdist = 0;  // 最大距离

        for (let i = 1; i < person.length; i++) {
          if (person[i] - person[i - 1] === 1) {  // 两个人之间没空位
            continue;
          }

          const dist = Math.floor((person[i] - person[i - 1]) / 2);

          if (dist > maxdist) {  // 相同区间取最小下标，因此=不需要更新
            maxdist = dist;
            pos = person[i - 1] + maxdist;
          }
        }

        if (setNum - 1 - person[person.length - 1] > maxdist) {  // 最后一个人的位置是否能坐人
          maxdist = setNum - 1 - person[person.length - 1];
          pos = person[person.length - 1] + maxdist;
        }

        if (pos !== -1) {
          person.push(pos);
          ans = pos;
          person.sort((a, b) => a - b);
        }
      }
    }

    console.log(ans);  // 输出结果

    rl.close();  // 关闭readline接口
  });
});

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int setNum = scanner.nextInt();
        scanner.nextLine(); // consume the newline character

        String s = scanner.nextLine();
        List<Integer> w = new ArrayList<>();

        StringBuilder t = new StringBuilder();
        for (int i = 1; i < s.length() - 1; i++) {
            if (s.charAt(i) == ',') {
                int num = Integer.parseInt(t.toString());
                w.add(num);
                t.setLength(0);
            } else {
                t.append(s.charAt(i));
            }
        }
        w.add(Integer.parseInt(t.toString()));

        List<Integer> person = new ArrayList<>();  // 已经就座的座位编号
        int ans = -1;

        for (int x : w) {
            if (x < 0) {  // 说明有人要离场
                int pos = -x;
                if (person.contains(pos)) {
                    person.remove(Integer.valueOf(pos));
                }
            } else if (x == 0) {
                continue;
            } else if (person.isEmpty()) {  // 座位没有坐人
                person.add(0);
                ans = 0;
            } else if (person.size() == 1) {   // 座位上只有一个人，那么第二个人一定是坐最右边
                person.add(setNum - 1);
                ans = setNum - 1;
            } else {
                int pos = -1;  // 新来的人坐的位置
                int maxDist = 0;  // 最大距离
                for (int i = 1; i < person.size(); i++) {  // 枚举每两个人之间的空位
                    if (person.get(i) - person.get(i - 1) == 1) {  // 两个人之间没空位
                        continue;
                    }
                    int dist = (person.get(i) - person.get(i - 1)) / 2;
                    if (dist > maxDist) {  // 相同区间取最小下标，因此=不需要更新
                        maxDist = dist;
                        pos = person.get(i - 1) + maxDist;
                    }
                }
                if (setNum - 1 - person.get(person.size() - 1) > maxDist) {  // 最后一个人的位置是否能坐人
                    maxDist = setNum - 1 - person.get(person.size() - 1);
                    pos = person.get(person.size() - 1) + maxDist;
                }
                if (pos != -1) {
                    person.add(pos);
                    ans = pos;
                    Collections.sort(person);
                }
            }
        }

        System.out.println(ans);
    }
}

Python

setNum=int(input())
w=list(map(int,input()[1:-1].split(',')))
person=[]  #已经就座的座位编号
ans=-1
for x in w:
    if x<0:  #说明有人要离场
        pos=-x
        if pos in person:
            idx=person.index(pos)  #找到对应编号
            person.pop(idx)
    elif x==0:
        continue
    elif len(person)==0:  #座位没有坐人
        person.append(0)
        ans=0
    elif len(person)==1:   #座位上只有一个人，那么第二个人一定是坐最右边
        person.append(setNum-1)
        ans=setNum-1
    else:
        pos=-1  #新来的人坐的位置
        maxdist=0  #最大距离
        for i in range(1,len(person)):  #枚举每两个人之间的空位
            if person[i]-person[i-1]==1:  #两个人之间没空位
                continue
            dist=(person[i]-person[i-1])//2
            if dist>maxdist:  #相同区间取最小下标，因此=不需要更新
                maxdist=dist
                pos=person[i-1]+maxdist
        if setNum-1-person[-1]>maxdist:  #最后一个人的位置是否能坐人
            maxdist=setNum-1-person
            pos=person[-1]+maxdist
        if pos!=-1:
            person.append(pos)
            ans=pos
            person.sort()

print(ans)

C++

#include<bits/stdc++.h>
using namespace std;

int main() {
    int setNum;
    cin >> setNum;

    vector<int> w;
    string s,t;
    cin>>s;
    for(int i=1;i<s.size()-1;i++){
        if(s[i]==','){
            int num=stoi(t,nullptr,10);
            w.push_back(num);
            t.clear();
        }
        else{
            t.push_back(s[i]);
        }
    }
    w.push_back(stoi(t,nullptr,10));
    vector<int> person;  // 已经就座的座位编号
    int ans = -1;

    for (int x : w) {
        if (x < 0) {  // 说明有人要离场
            int pos = -x;
            auto it = find(person.begin(), person.end(), pos);
            if (it != person.end()) {
                person.erase(it);
            }
        } else if (x == 0) {
            continue;
        } else if (person.empty()) {  // 座位没有坐人
            person.push_back(0);
            ans = 0;
        } else if (person.size() == 1) {   // 座位上只有一个人，那么第二个人一定是坐最右边
            person.push_back(setNum - 1);
            ans = setNum - 1;
        } else {
            int pos = -1;  // 新来的人坐的位置
            int maxDist = 0;  // 最大距离
            for (int i = 1; i < person.size(); i++) {  // 枚举每两个人之间的空位
                if (person[i] - person[i - 1] == 1) {  // 两个人之间没空位
                    continue;
                }
                int dist = (person[i] - person[i - 1]) / 2;
                if (dist > maxDist) {  // 相同区间取最小下标，因此=不需要更新
                    maxDist = dist;
                    pos = person[i - 1] + maxDist;
                }
            }
            if (setNum - 1 - person.back() > maxDist) {  // 最后一个人的位置是否能坐人
                maxDist = setNum - 1 - person.back();
                pos = person.back() + maxDist;
            }
            if (pos != -1) {
                person.push_back(pos);
                ans = pos;
                sort(person.begin(), person.end());
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

题目描述

疫情期间需要大家保持一定的社交距离，公司组织开交流会议。

座位一排共 $N$ 个座位，编号分别为[$0,N-1$]。

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

满足：

每当一个员工进入时，需要坐到最大社交距离（最大化自己和其他人的距离的座位）；

如果有多个这样的座位，则坐到索引最小的那个座位。

输入描述

会议座位总数 $seatNum$。$1 \le seatNum \le 500$.

员工的进出顺序 $seatOrLeave$ 数组 。

元素值为 $1$ ，表示进场

元素值为负数，表示出场（特殊：位置 $0$ 的员工不会离开）

例如 $-4$ 表示坐在位置 $4$ 的员工离开（保证所有员工坐在该座位上）

输出描述

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

用例

输入

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

输出

5

说明：

$seat -> 0$， 空在任何位置都行，但是要给他安排索引最小的位置，也就是座位 $0$

$seat -> 9$, 要和旁边的人距离最远，也就是座位 $9$

$seat -> 4$，要和旁边的人距离最远，应该是坐到中间，也就是座位 $4$

$seat -> 2$ ,员工最后坐在位置 $2$ 号座位上

$leave[4]$ ，$4$ 号座位的员工离开

$seat -> 5$ , 员工最后坐在 5 号座位上