题目描述
小明在玩一款战争游戏。地图上一共有N
个敌方单位,可以看作 2D 平面上的点。其中第
i
个单位在 0 时刻的位置是(Xi
,Yi
),方向是Di
(上下左右之一, 用’U’/’D’/’L’/’R’ 表示),速度是 Vi
。
小明的武器是轨道炮,只能使用一次,不过杀伤力巨大。小明可以选择在某个非负整数时刻释放轨道炮,轨道炮一次可以消灭在一条直线 (平行于坐标轴)上的所有敌方单位。
请你计算小明最多能消灭多少敌方单位。
输入描述
输入第一行包含一个整数 N
以下 N 行每行包含 3 个整数 Xi
Yi
Vi
以及一个大写字符 Di
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L
输出
3
数据很水,暴力枚举0-1000s就可以
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
#define x first
#define y second
#define v first
#define d second
int n;
pair<pair<int, int>, pair<int, int>> point[N]; // 第一对是x,y 第二对是v,d
unordered_map<char, int> direction = {{'U', 1}, {'D', 2}, {'L', 3}, {'R', 4}};
unordered_map<int, int> qx, qy;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int px, py, pv;
char pd;
cin >> px >> py >> pv >> pd;
point[i] = {{px, py}, {pv, direction[pd]}};
}
int ans = 0;
for (int t = 0; t <= 1000; t++)
{
qx.clear();
qy.clear();
for (int i = 0; i < n; i++)
{
int cx, cy;
if (point[i].second.d >= 3)
{
cy = point[i].first.y;
if (point[i].second.d == 3)
cx = point[i].first.x - t * point[i].second.v;
else
cx = point[i].first.x + t * point[i].second.v;
}
else
{
cx = point[i].first.x;
if (point[i].second.d == 1)
cy = point[i].first.y + t * point[i].second.v;
else
cy = point[i].first.y - t * point[i].second.v;
}
qx[cx]++, qy[cy]++;
}
for (auto &[u, v] : qx)
ans = max(ans, v);
for (auto &[u, v] : qy)
ans = max(ans, v);
}
cout << ans << '\n';
//system("pause");
return 0;
}