题目描述
在无限大的棋盘中有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. 主要思路
为了高效求解，可以采用 哈希表 + 排序 的方法：
使用哈希表分类存储炮的位置：
- 用 unordered_map<int, vector<pair<int, int>>> rows 存储 同一行 的炮，key 为 行号，value 为 （列号，炮的索引）。
- 用 unordered_map<int, vector<pair<int, int>>> cols 存储 同一列 的炮，key 为 列号，value 为 （行号，炮的索引）。
对每一行、每一列的炮进行排序：
- 按照 列号 对同一行的炮进行排序，遍历后计算每个炮的可攻击数量。
- 按照 行号 对同一列的炮进行排序，遍历后计算每个炮的可攻击数量。
计算每个炮的攻击目标：
- 经过排序后，我们遍历 每一行，如果某个炮 左侧第二个 存在，它可以攻击左侧目标；如果 右侧第二个 存在，它可以攻击右侧目标。
- 同样遍历 每一列，如果某个炮 上侧第二个 存在，它可以攻击上侧目标；如果 下侧第二个 存在，它可以攻击下侧目标。
输出结果：每个炮能攻击到的炮的总数。
时间复杂度分析
构造哈希表 需要遍历所有炮，时间复杂度为 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)。
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏