题目描述

在无限大的棋盘中有n个炮，第个炮的坐标是(xi,yi)。

已知每个炮的攻击方式是:先选一个攻击方向(上、下、左、右），该方向上看见的第一个棋子为“炮架”，该炮可以通过炮架攻击到炮架后面的棋子(只能攻击到炮架后面的第一个)。

小牛希望你求出每个炮第一次攻击能攻击到多少个炮。

输入描述

第一行输入一个正整数n，代表炮的数量。
接下来的几行，每行输入两个整数xi,yi，代表每个炮所在的坐标。
1<=n<=10^5
-10^9 <=xi,yi<= 10^9

输出描述

输出几行，每行输出一个整数，代表第i个炮可以攻击到的炮的数量。

示例1

输入：
6 
0 0 
0 1 
0 2 
1 0 
2 0 
3 0输出：
2
0
1
1
1
1

C++

#include <bits/stdc++.h>using namespace std;// 记录同一行的所有炮，key为行号，value为<列号, 炮的序号>
unordered_map<int, vector<pair<int, int>>> rows;
// 记录同一列的所有炮，key为列号，value为<行号, 炮的序号>
unordered_map<int, vector<pair<int, int>>> cols;int main() {int n;cin >> n;// 记录每个炮的攻击目标数vector<int> ans(n);// 读取输入数据for (int i = 0, x, y; i < n; i++) {cin >> x >> y;rows[x].emplace_back(y, i); // 按行分类，存储列号和炮的索引cols[y].emplace_back(x, i); // 按列分类，存储行号和炮的索引}// 遍历所有行，统计每个炮能攻击到的炮for (auto &p: rows) {vector<pair<int, int>> &lst = p.second;sort(lst.begin(), lst.end()); // 按列号排序for (int i = 0; i < lst.size(); i++) {int idx = lst[i].second;// 如果该炮右侧有两个炮，则可以攻击右侧if (i + 2 < lst.size()) ans[idx]++;// 如果该炮左侧有两个炮，则可以攻击左侧if (i - 2 >= 0) ans[idx]++;}}// 遍历所有列，统计每个炮能攻击到的炮for (auto &p: cols) {vector<pair<int, int>> &lst = p.second;sort(lst.begin(), lst.end()); // 按行号排序for (int i = 0; i < lst.size(); i++) {int idx = lst[i].second;// 如果该炮下侧有两个炮，则可以攻击下侧if (i + 2 < lst.size()) ans[idx]++;// 如果该炮上侧有两个炮，则可以攻击上侧if (i - 2 >= 0) ans[idx]++;}}// 输出每个炮能攻击的目标数for (int cnt: ans) {cout << cnt << endl;}return 0;
}

题目类型

本题属于 哈希表 + 排序 结合的题目，同时具有 扫描线思想，因为我们需要分别统计同一行和同一列上的炮的情况，以确定每个炮的攻击目标。

---

解题思路

1. 题目解析

• 题目给定 n 个炮的坐标，炮的攻击方式是在选择一个方向（上、下、左、右）后，找到该方向上的 第一个棋子作为炮架，然后攻击炮架后面 最近的炮。
• 需要计算 每个炮可以攻击到的炮的数量。

2. 主要思路

为了高效求解，可以采用 哈希表 + 排序 的方法：

1. 使用哈希表分类存储炮的位置：

   • 用 unordered_map<int, vector<pair<int, int>>> rows 存储 同一行 的炮，key 为 行号，value 为 （列号，炮的索引）。
   • 用 unordered_map<int, vector<pair<int, int>>> cols 存储 同一列 的炮，key 为 列号，value 为 （行号，炮的索引）。

2. 对每一行、每一列的炮进行排序：

   • 按照 列号 对同一行的炮进行排序，遍历后计算每个炮的可攻击数量。
   • 按照 行号 对同一列的炮进行排序，遍历后计算每个炮的可攻击数量。

3. 计算每个炮的攻击目标：

   • 经过排序后，我们遍历 每一行，如果某个炮 左侧第二个 存在，它可以攻击左侧目标；如果 右侧第二个 存在，它可以攻击右侧目标。
   • 同样遍历 每一列，如果某个炮 上侧第二个 存在，它可以攻击上侧目标；如果 下侧第二个 存在，它可以攻击下侧目标。

4. 输出结果：每个炮能攻击到的炮的总数。

时间复杂度分析

• 构造哈希表 需要遍历所有炮，时间复杂度为 O(n)。

• 排序部分：

  • 每个行/列最多包含 n 个元素，排序的时间复杂度为 O(k log k)，其中 k 是该行/列的炮的数量。

• 由于最坏情况下 所有炮都在同一行或同一列，排序时间复杂度为 O(n log n)。

  • 遍历计算攻击目标 也是 O(n)。

  综上，总时间复杂度为 O(n log n)，可以高效处理 n ≤ 10^5 的情况。

---

空间复杂度分析

• 哈希表 rows 和 cols：在最坏情况下，所有炮分布在同一行或列，存储 O(n) 个元素。
• 数组 ans：大小为 O(n)。
• 排序的临时空间：排序 O(1) 额外空间。

综上，总空间复杂度为 O(n)。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏