算法标签

• 贪心（Greedy）
• 模拟（Simulation）
• 对称性处理
• 约束满足

问题分析

我们有 $n$ 排，每排 $6$ 个座位，编号 $1$ 到 $6$。
对称规则是：

• 座位 $1$ 与 $6$ 对称
• 座位 $2$ 与 $5$ 对称
• 座位 $3$ 与 $4$ 对称

如果某一边的座位被占用，则对称的另一边也必须被占用（最终状态）。

初始时，某些座位被在线选座（X 表示已占，. 表示空）。
我们需要再安排 $m$ 个乘客到空座位上，使得最终满足对称条件。

关键观察

1. 对称性检查
   如果初始时座位 $i$ 被占，而对称座位 $j$ 为空，则必须安排一个乘客到 $j$ 上（强制安排）。
   如果对称的两个座位都空，则我们可以选择安排 $0$ 个、$1$ 个或 $2$ 个乘客到这对座位上（安排 $1$ 个是不允许的，因为不对称）。

2. 分类讨论
   对于每一排，我们可以把 6 个座位分成 3 对：

   • 对 1：座位 1 与 6
   • 对 2：座位 2 与 5
   • 对 3：座位 3 与 4

   每对的状态：

   • 类型 A：两个座位都空 → 可以安排 0 人或 2 人
   • 类型 B：一个座位被占，另一个空 → 必须安排 1 人到空位（强制）
   • 类型 C：两个座位都被占 → 不能安排人

3. 强制安排
   首先统计所有类型 B 的对数，这些必须安排乘客，否则无法对称。
   设这个数量为 must。
   如果 must > m，则不可能（因为必须安排的人数已经超过 $m$）。

4. 剩余安排
   安排完 must 个乘客后，剩下 m - must 个乘客。
   这些乘客必须成对安排（因为只能安排到类型 A 的对中，每对需要 2 人）。
   所以 m - must 必须是偶数。

5. 容量检查
   类型 A 的对数记为 freePairs。
   最多能安排 2 * freePairs 个乘客到类型 A 对。
   所以必须满足：
   [ m - must \le 2 \times freePairs ] 并且 (m - must) 是偶数。

构造方案

如果检查通过，我们可以这样构造：

1. 先处理类型 B：对每个类型 B，在空座位上安排一个乘客。
2. 再处理类型 A：用剩下的乘客成对安排到类型 A 对中，直到用完。
3. 输出最终座位图。

算法步骤

1. 读入 $n, m$ 和初始座位图。
2. 对每一排，检查三对座位，统计：
   • must：类型 B 的数量
   • freePairs：类型 A 的数量
   • 记录哪些座位是强制安排的
3. 检查可行性：
   • 如果 must > m → Impossible
   • 如果 (m - must) 是奇数 → Impossible
   • 如果 m - must > 2 * freePairs → Impossible
4. 否则，构造方案：
   • 先安排 must 个乘客到类型 B 的空位
   • 再安排 (m - must) / 2 对乘客到类型 A 对
5. 输出最终座位图。

样例验证

以样例 5 为例：

初始：

X.....
......
....X.
X.....
......
..XX..

对称对分析（略过详细推导），经过计算满足条件，可以安排 7 人，最终输出如题所示。

时间复杂度

• 每排处理 $O(1)$
• 总复杂度 $O(n)$
• 满足 $n \le 1000$ 的要求

代码框架（伪代码）

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    int must = 0;
    int free_pairs = 0;
    
    // 第一遍：统计 must 和 free_pairs
    for (int i = 0; i < n; i++) {
        // 三对对称座位 (0-based索引)
        pair<int, int> pairs[3] = {{0, 5}, {1, 4}, {2, 3}};
        
        for (int j = 0; j < 3; j++) {
            int a = pairs[j].first;
            int b = pairs[j].second;
            
            if (grid[i][a] == 'X' && grid[i][b] == '.') {
                must++;
            } else if (grid[i][a] == '.' && grid[i][b] == 'X') {
                must++;
            } else if (grid[i][a] == '.' && grid[i][b] == '.') {
                free_pairs++;
            }
        }
    }
    
    // 检查可行性
    if (must > m || (m - must) % 2 != 0 || (m - must) > 2 * free_pairs) {
        cout << "Impossible" << endl;
    } else {
        int remaining = m;
        
        // 先安排必须的座位
        for (int i = 0; i < n; i++) {
            pair<int, int> pairs[3] = {{0, 5}, {1, 4}, {2, 3}};
            
            for (int j = 0; j < 3; j++) {
                int a = pairs[j].first;
                int b = pairs[j].second;
                
                if (remaining > 0) {
                    if ((grid[i][a] == 'X' && grid[i][b] == '.') || 
                        (grid[i][a] == '.' && grid[i][b] == 'X')) {
                        
                        if (grid[i][a] == '.') {
                            grid[i][a] = 'X';
                        } else {
                            grid[i][b] = 'X';
                        }
                        remaining--;
                    }
                }
            }
        }
        
        // 再成对安排剩余乘客
        for (int i = 0; i < n; i++) {
            pair<int, int> pairs[3] = {{0, 5}, {1, 4}, {2, 3}};
            
            for (int j = 0; j < 3; j++) {
                int a = pairs[j].first;
                int b = pairs[j].second;
                
                if (remaining >= 2 && grid[i][a] == '.' && grid[i][b] == '.') {
                    grid[i][a] = 'X';
                    grid[i][b] = 'X';
                    remaining -= 2;
                }
            }
        }
        
        // 输出结果
        for (int i = 0; i < n; i++) {
            cout << grid[i] << endl;
        }
    }
    
    return 0;
}