[蓝桥杯]轨道炮

轨道炮

题目描述

小明在玩一款战争游戏。地图上一共有 NN 个敌方单位，可以看作 2D 平面上的点。其中第 ii 个单位在 0 时刻的位置是 (Xi,Yi)(Xi​,Yi​)，方向是 DiDi​ (上下左右之一, 用'U'/'D'/'L'/'R' 表示)，速度是 ViVi​。

小明的武器是轨道炮，只能使用一次，不过杀伤力巨大。小明可以选择在某个非负整数时刻释放轨道炮，轨道炮一次可以消灭在一条直线 (平行于坐标轴)上的所有敌方单位。

请你计算小明最多能消灭多少敌方单位。

输入描述

输入第一行包含一个整数 NN。

以下 NN 行每行包含 3 个整数 Xi,Yi,ViXi​,Yi​,Vi​，以及一个大写字符 DiDi​。

其中，1≤N≤1000，−106≤Xi,Yi≤106，0≤Vi≤1061≤N≤1000，−106≤Xi​,Yi​≤106，0≤Vi​≤106。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L

输出

3

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 400  |  总提交次数: 544  |  通过率: 73.5%

难度: 困难   标签: 2019, 模拟, 贪心, 国赛

算法思路：坐标分组 + 时间枚举

我们需要找到​​一个整数时刻 t​​ 和​​一条平行于坐标轴的直线​​，使得该直线上敌方单位数量最大化。核心思路如下：

1. ​​运动分解​​：

   • 每个单位在时刻 t 的位置由其初始位置和运动方向决定：
     • R/L：水平移动（x 变化，y 不变）
     • U/D：垂直移动（y 变化，x 不变）
   • 位置公式：
     • x(t)=Xi​±Vi​⋅t（水平移动）
     • y(t)=Yi​±Vi​⋅t（垂直移动）

2. ​​分组统计​​：

   • ​​垂直轨道炮（x=c）​​：统计所有单位在 t 时刻的 x 坐标
   • ​​水平轨道炮（y=c）​​：统计所有单位在 t 时刻的 y 坐标
   • 最终答案为两种轨道炮消灭单位数的最大值

3. ​​关键优化​​：

   • 通过枚举单位对 (i, j) 计算相遇时间 t：
     • 若速度相同：仅当初始位置重合时始终满足条件
     • 若速度不同：解方程 Xi​+Vxi​​⋅t=Xj​+Vxj​​⋅t（x 方向）
   • 使用 unordered_map 记录每个时刻 t 的重合单位数

C++代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;int n, mx = 0;// 处理单方向（x或y）
void solve(vector<int>& pos, vector<int>& vel) {for (int i = 0; i < n; ++i) {int cnt = 1;  // 至少包含当前单位iunordered_map<int, int> timeCount; // 记录各时间点的重合数for (int j = i + 1; j < n; ++j) {if (vel[i] == vel[j]) {if (pos[i] == pos[j]) cnt++;mx = max(mx, cnt);} else {int dp = pos[i] - pos[j];int dv = vel[j] - vel[i];// 检查t=dp/dv是否为非负整数if (dv == 0) continue;if (dp % dv != 0) continue;int t = dp / dv;if (t < 0) continue;timeCount[t]++;mx = max(mx, timeCount[t] + cnt);}}}
}int main() {cin >> n;vector<int> X(n), Y(n), V(n);vector<char> D(n);// 读入数据for (int i = 0; i < n; ++i) {cin >> X[i] >> Y[i] >> V[i] >> D[i];}// 初始化方向速度分量vector<int> vx(n, 0), vy(n, 0);for (int i = 0; i < n; ++i) {switch (D[i]) {case 'R': vx[i] = V[i]; break;case 'L': vx[i] = -V[i]; break;case 'U': vy[i] = V[i]; break;case 'D': vy[i] = -V[i]; break;}}// 分别处理x方向和y方向solve(X, vx); // 垂直轨道炮（x=c）int res_x = mx;mx = 0;solve(Y, vy); // 水平轨道炮（y=c）int res_y = mx;cout << max(res_x, res_y) << endl;return 0;
}

代码解析

1. ​​数据结构​​：

   • X, Y, V, D：存储单位初始位置、速度、方向
   • vx, vy：速度分量（水平/垂直方向）

2. ​​核心函数 solve​​：

   • ​​双层循环​​：枚举所有单位对 (i, j)
   • ​​速度相同处理​​（vel[i]==vel[j]）：
     • 位置相同时计数器 cnt++
   • ​​速度不同处理​​：
     • 解方程 dp=posi​−posj​，dv=velj​−veli​
     • 验证 t=dp/dv 为​​非负整数​​
     • 通过 timeCount 哈希表记录各时刻重合数

3. ​​方向处理逻辑​​：

   • 垂直轨道炮：传入 X, vx（x坐标和水平速度）
   • 水平轨道炮：传入 Y, vy（y坐标和垂直速度）

实例验证

​​输入​​：

4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L

​​执行流程​​：

1. ​​垂直轨道炮（x方向）​​：

   • 单位1和2：速度相同（vx=1）且初始x=0 → cnt=2
   • 单位1和3：t=(0-10)/(0-1)=10 → 记录 timeCount[10]=1
   • 单位2和3：t=(0-10)/(0-1)=10 → timeCount[10]=2
   • ​​最大值​​：timeCount[10] + cnt = 2+2 = 3

2. ​​水平轨道炮（y方向）​​：

   • 无初始重合单位
   • 单位1和3：y坐标在t=5时重合（0+0=10-2×5）
   • ​​最大值​​：2（单位1和3）

3. ​​最终输出​​：max(3, 2) = 3

测试点设计

测试类型	样例输入	预期输出	验证要点
基础案例	题目示例	3	常规功能
全静止单位	所有V=0	按初始位置分组	速度相同处理
同向同速	所有D='R', V相同	按初始x坐标分组	速度相同逻辑
大范围坐标	X/Y=±1e6, V=1e6	不超时	整数除法优化
无重合	单位分散	1	边界情况

优化建议

1. ​​时间复杂度​​：

   • 当前复杂度 O(N2)，N=1000 时 50 万次循环
   • 可用 std::gcd 优化整除判断：

     if (dp % dv != 0) → if (dp % abs(gcd) != 0)

2. ​​空间优化​​：

   • 用 vector 替代哈希表存储预计算的时间点
   • 分方向独立处理减少内存占用

3. ​​工程实践​​：

   • 添加输入验证（坐标范围 -1e6~1e6）
   • 使用 long long 防止乘法溢出