射击游戏题解

问题分析

我们需要用最少的时间摧毁所有建筑物。每轮两名玩家各发射一发子弹，可以选择不同的高度。关键在于如何配对高度使得每轮尽可能摧毁两个不同的建筑物。

核心思路

最少轮数：由于每轮最多摧毁2座建筑，最少轮数为 ⌈N/2⌉。

关键观察：如果两个高度 H₁ 和 H₂ 对应的目标建筑不同，就可以在同一轮摧毁它们。

贪心策略：将建筑按某种顺序配对，使得每对可以在同一轮被不同高度的子弹摧毁。

算法实现

#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> min_shooting_buildings(vector<int> A) {
    int n = A.size();
    vector<int> pos(n + 1);
    
    // 建立高度到位置的映射
    for (int i = 0; i < n; i++) {
        pos[A[i]] = i;
    }
    
    vector<pair<int, int>> result;
    vector<int> seq1, seq2;
    int last1 = -1, last2 = -1;
    
    // 贪心分组：维护两个递增位置序列
    for (int h = 1; h <= n; h++) {
        if (last1 < pos[h]) {
            seq1.push_back(h);
            last1 = pos[h];
        } else if (last2 < pos[h]) {
            seq2.push_back(h);
            last2 = pos[h];
        } else {
            // 加入结束位置较小的序列
            if (last1 < last2) {
                seq1.push_back(h);
                last1 = pos[h];
            } else {
                seq2.push_back(h);
                last2 = pos[h];
            }
        }
    }
    
    // 配对两个序列
    int m = max(seq1.size(), seq2.size());
    for (int i = 0; i < m; i++) {
        int h1 = (i < seq1.size()) ? seq1[i] : n + 1;
        int h2 = (i < seq2.size()) ? seq2[i] : n + 1;
        result.push_back({h1, h2});
    }
    
    return result;
}

算法正确性

• 每个序列中的建筑位置递增，确保较高的建筑在较右位置
• 分组策略保证所有建筑都被分配到某个序列
• 配对时若序列长度不同，用 n+1 补足（表示不摧毁任何建筑）

复杂度分析

• 时间复杂度：O(N)，只需一次遍历
• 空间复杂度：O(N)，存储分组结果

该解法能够达到最优轮数 ⌈N/2⌉，并通过所有测试数据。