算法标签

• 数据结构：有序集合 (set/平衡树)
• 模拟
• 贪心
• 区间处理

题目分析

这是一个典型的动态座位选择问题，需要维护当前被占用的座位集合，并在每次有新乘客进入时，快速找到距离其他乘客最远的空座位。

关键观察

1. 座位布局特殊：只有2列，N行，这大大简化了问题
2. 距离计算：欧几里得距离，但由于只有2列，最近距离通常来自同一行或相邻行的已占座位
3. 选择策略：最大化最小距离，具有贪心性质

高效解法

核心思路

使用有序集合（如C++的set）维护当前被占用的座位（按行号排序）。对于每个新乘客：

1. 处理边界情况：如果电车为空，直接返回(1,1)
2. 生成候选座位：考虑所有相邻已占座位之间的区间
3. 评估候选：在每个区间中，最优点通常出现在区间中点附近
4. 选择最优：比较所有候选座位，选择距离最大的

算法步骤

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

// 计算两个座位间的距离
double dist(int r1, int c1, int r2, int c2) {
    return sqrt((r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2));
}

int main() {
    int N, M;
    cin >> N >> M;
    
    set<pair<int, int>> occ; // 被占用的座位 (行, 列)
    // 添加虚拟边界座位，便于处理第一个和最后一个区间
    occ.insert({0, 1});
    occ.insert({N + 1, 1});
    
    vector<pair<int, int>> seatOf(M + 1); // 记录每个事件对应的座位
    
    for (int k = 1; k <= M; k++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            // 电车为空的情况
            if (occ.size() == 2) {
                seatOf[k] = {1, 1};
                occ.insert({1, 1});
                cout << "1 1\n";
                continue;
            }
            
            double bestDist = -1;
            pair<int, int> bestSeat = {-1, -1};
            
            // 遍历所有相邻的已占座位对（形成区间）
            auto it1 = occ.begin();
            auto it2 = occ.begin();
            ++it2;
            
            while (it2 != occ.end()) {
                int r1 = it1->first, c1 = it1->second;
                int r2 = it2->first, c2 = it2->second;
                
                // 区间 [r1+1, r2-1] 内的空座位
                if (r1 + 1 <= r2 - 1) {
                    // 检查区间中点附近的几行
                    int mid = (r1 + r2) / 2;
                    for (int r = max(r1 + 1, mid - 2); r <= min(r2 - 1, mid + 2); r++) {
                        for (int col = 1; col <= 2; col++) {
                            if (occ.count({r, col})) continue;
                            
                            // 计算到最近已占座位的距离
                            double minD = 1e9;
                            for (auto &p : occ) {
                                double d = dist(r, col, p.first, p.second);
                                if (d < minD) minD = d;
                            }
                            
                            // 更新最优座位
                            if (minD > bestDist + 1e-9 || 
                                (abs(minD - bestDist) < 1e-9 && 
                                 (r < bestSeat.first || (r == bestSeat.first && col < bestSeat.second)))) {
                                bestDist = minD;
                                bestSeat = {r, col};
                            }
                        }
                    }
                }
                
                ++it1;
                ++it2;
            }
            
            seatOf[k] = bestSeat;
            occ.insert(bestSeat);
            cout << bestSeat.first << " " << bestSeat.second << "\n";
            
        } else { // 类型 L：乘客离开
            int p;
            cin >> p;
            occ.erase(seatOf[p]); // 从占用集合中移除座位
        }
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：平均 O(M × K)，其中 K 是平均的已占座位数
• 空间复杂度：O(M) 存储座位信息