解题思路

这是一道经典的贪心算法与模拟题目。我们需要维护一个有序的数据结构来存储当前被占用的座位索引，以便快速计算相邻座位之间的距离。

1. 数据结构选择： 由于需要频繁地插入座位、删除座位以及遍历当前有序的座位列表来计算间距，使用有序集合（Ordered Set）是最合适的。

   • 在 Python 中，可以使用列表 list 配合排序（因为 $N$ 较小，每次插入后排序或直接遍历的时间成本可以接受）。
   • 在 Java 中，可以使用 TreeSet。
   • 在 C++ 中，可以使用 std::set。

2. 入场逻辑（贪心策略）： 当一名员工（操作为 1）进场时，我们需要找到一个位置 $x$，使得该位置到最近的已占用座位的距离最大。如果距离相同，则选择索引最小的座位。

   我们需要考虑以下三种候选位置区间：

   • 最左侧：如果座位 $0$ 未被占用，候选位置为 $0$，距离为 seats[0] - 0（即第一个已占用座位的索引）。
   • 中间空隙：对于任意两个相邻的已占用座位 $left$ 和 $right$，在它们中间就座的最大距离位置是 $pos = \lfloor (left + right) / 2 \rfloor$。该位置到最近邻居的距离为 $pos - left$。
   • 最右侧：如果座位 $N-1$ 未被占用，候选位置为 $N-1$，距离为 (N - 1) - seats[last]（即最后一个已占用座位）。

   我们遍历上述所有情况，维护一个 max_dist（最大距离）和 best_pos（最佳位置）。如果发现更大的距离，更新两者；如果距离等于当前最大距离，由于我们是按索引从小到大扫描的（先看0，再看中间，最后看N-1），保持原有的 best_pos 不变即可满足“索引最小”的要求（注：在中间空隙计算中，如果计算出的距离严格大于当前最大距离才更新，这样能保证距离相同时保留索引更小的结果）。

   特殊情况：如果会议室全空，直接坐在位置 $0$。如果会议室已满，返回 $-1$。

3. 离场逻辑： 当输入为负数（如 $-4$）时，直接从有序集合中移除对应的正数索引（即 $4$）。

4. 处理流程： 解析输入字符串为操作数组，遍历数组。如果是入场操作，计算最佳位置并加入集合，记录结果；如果是离场操作，从集合中移除。最终输出最后一次入场操作分配的座位号。

复杂度分析

• 时间复杂度： 假设座位总数为 $N$，操作序列长度为 $M$。

  • 对于每次入场操作，我们需要遍历当前已占用的座位列表。最坏情况下已占用 $N$ 个座位，单次查找复杂度为 $O(N)$。
  • 对于离场操作，集合删除通常为 $O(\log N)$ 或 $O(N)$。
  • 总时间复杂度为 $O(M \cdot N)$。鉴于 $N \le 500$，计算量非常小，完全满足要求。

• 空间复杂度： 我们需要存储已占用的座位，空间复杂度为 $O(N)$。

代码实现

Python

import sys

def solve():
    # 读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    # 解析座位总数 N
    n = int(input_data[0])
    
    # 解析操作数组
    # 输入格式如 [1,1,1,1,-4,1]，需要去除方括号并按逗号分割
    ops_str = input_data[1]
    ops_str = ops_str.strip('[]')
    if not ops_str:
        ops_list = []
    else:
        ops_list = list(map(int, ops_str.split(',')))

    occupied = [] # 存储已占用的座位，保持有序
    last_seat_assigned = -1

    for op in ops_list:
        if op == 1:
            # 进场逻辑
            if len(occupied) == n:
                last_seat_assigned = -1
                continue
                
            if not occupied:
                # 如果没有人在，坐位置 0
                best_pos = 0
            else:
                best_dist = -1
                best_pos = -1
                
                # 1. 检查最左边 (0 到 第一个人)
                if occupied[0] != 0:
                    dist = occupied[0]
                    if dist > best_dist:
                        best_dist = dist
                        best_pos = 0
                
                # 2. 检查中间的所有间隙
                for i in range(len(occupied) - 1):
                    left = occupied[i]
                    right = occupied[i+1]
                    # 中间位置
                    mid = (left + right) // 2
                    # 距离左边的距离（也就是到最近人的距离）
                    dist = mid - left
                    
                    if dist > best_dist:
                        best_dist = dist
                        best_pos = mid
                
                # 3. 检查最右边 (最后一个人 到 N-1)
                if occupied[-1] != n - 1:
                    dist = (n - 1) - occupied[-1]
                    if dist > best_dist:
                        best_dist = dist
                        best_pos = n - 1
            
            # 坐下
            occupied.append(best_pos)
            occupied.sort()
            last_seat_assigned = best_pos
            
        else:
            # 离场逻辑，op 是负数，例如 -4 表示位置 4 离开
            seat_to_leave = -op
            if seat_to_leave in occupied:
                occupied.remove(seat_to_leave)

    print(last_seat_assigned)

if __name__ == "__main__":
    solve()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNext()) return;

        // 读取座位总数
        int n = Integer.parseInt(sc.nextLine().trim());
        
        // 读取操作数组字符串
        String line = sc.nextLine().trim();
        // 去除方括号
        line = line.substring(1, line.length() - 1);
        
        String[] parts = line.split(",");
        int[] ops = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            ops[i] = Integer.parseInt(parts[i].trim());
        }

        // 使用 TreeSet 保持座位有序
        TreeSet<Integer> occupied = new TreeSet<>();
        int lastSeatAssigned = -1;

        for (int op : ops) {
            if (op == 1) {
                // 进场
                if (occupied.size() == n) {
                    lastSeatAssigned = -1;
                    continue;
                }

                int bestPos = -1;
                int bestDist = -1;

                // 1. 检查位置 0
                if (occupied.isEmpty()) {
                    bestPos = 0;
                } else {
                    // 检查开头空隙
                    int first = occupied.first();
                    if (first > 0) {
                        int dist = first; // dist = first - 0
                        if (dist > bestDist) {
                            bestDist = dist;
                            bestPos = 0;
                        }
                    }

                    // 检查中间空隙
                    Iterator<Integer> it = occupied.iterator();
                    int prev = it.next();
                    while (it.hasNext()) {
                        int curr = it.next();
                        int mid = (prev + curr) / 2;
                        int dist = mid - prev;
                        // 这里使用 > 而不是 >=，保证距离相同时取索引较小的（因为我们是从左向右扫描）
                        if (dist > bestDist) {
                            bestDist = dist;
                            bestPos = mid;
                        }
                        prev = curr;
                    }

                    // 检查末尾空隙
                    int last = occupied.last();
                    if (last < n - 1) {
                        int dist = (n - 1) - last;
                        if (dist > bestDist) {
                            bestDist = dist;
                            bestPos = n - 1;
                        }
                    }
                }

                occupied.add(bestPos);
                lastSeatAssigned = bestPos;

            } else {
                // 离场，op 为负数
                int seatToLeave = -op;
                occupied.remove(seatToLeave);
            }
        }

        System.out.println(lastSeatAssigned);
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    string line;
    // 读取换行符
    getline(cin, line); 
    // 读取数组字符串
    getline(cin, line);

    // 解析数组字符串 [1,1,-4,...]
    // 简单的解析方法：将 [ ] , 替换为空格，然后用 stringstream
    for (char &c : line) {
        if (c == '[' || c == ']' || c == ',') {
            c = ' ';
        }
    }

    stringstream ss(line);
    int op;
    vector<int> ops;
    while (ss >> op) {
        ops.push_back(op);
    }

    set<int> occupied;
    int last_seat_assigned = -1;

    for (int action : ops) {
        if (action == 1) {
            // 进场逻辑
            if (occupied.size() == n) {
                last_seat_assigned = -1;
                continue;
            }

            if (occupied.empty()) {
                occupied.insert(0);
                last_seat_assigned = 0;
            } else {
                int best_pos = -1;
                int best_dist = -1;

                // 1. 检查位置 0
                int first = *occupied.begin();
                if (first != 0) {
                    int dist = first;
                    if (dist > best_dist) {
                        best_dist = dist;
                        best_pos = 0;
                    }
                }

                // 2. 检查中间间隙
                auto it = occupied.begin();
                int prev = *it;
                ++it;
                while (it != occupied.end()) {
                    int curr = *it;
                    int mid = (prev + curr) / 2;
                    int dist = mid - prev;
                    
                    if (dist > best_dist) {
                        best_dist = dist;
                        best_pos = mid;
                    }
                    prev = curr;
                    ++it;
                }

                // 3. 检查位置 N-1
                int last = *occupied.rbegin();
                if (last != n - 1) {
                    int dist = (n - 1) - last;
                    if (dist > best_dist) {
                        best_dist = dist;
                        best_pos = n - 1;
                    }
                }

                occupied.insert(best_pos);
                last_seat_assigned = best_pos;
            }
        } else {
            // 离场逻辑
            int seat_to_leave = -action;
            occupied.erase(seat_to_leave);
        }
    }

    cout << last_seat_assigned << 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 号座位上