您的位置:首页 > 娱乐 > 八卦 > 宁波seo网络推广优质团队_桂林漓江景区介绍_百度电话号码查询_重庆网站seo技术

宁波seo网络推广优质团队_桂林漓江景区介绍_百度电话号码查询_重庆网站seo技术

2025/3/15 3:09:59 来源:https://blog.csdn.net/user_longling/article/details/146224334  浏览:    关键词:宁波seo网络推广优质团队_桂林漓江景区介绍_百度电话号码查询_重庆网站seo技术
宁波seo网络推广优质团队_桂林漓江景区介绍_百度电话号码查询_重庆网站seo技术

题目描述

在无限大的棋盘中有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 的情况。


空间复杂度分析

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

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

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com