蓝桥杯VIP算法训练-轨道炮-看完秒懂的（c++map）_蓝桥杯 轨道炮c++-CSDN博客

　　题目描述

　　小明在玩一款战争游戏。地图上一共有 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

　　提示

　　对于所有评测用例，1 ≤ N ≤ 1000， 1000000 ≤ Xi, Yi ≤ 1000000，0 ≤ Vi ≤1000000。

　　看题找算法:

　　典型map题目 思路：

　　1.首先横向射和纵向射是分立的问题，可以分别解决然后取最大值。

　　2.单个方向上问题就是：给定初始位置和速度，求一个时间和位置使得在这个时间和位置上重合的点最多。

　　3.因为n只有1000，两两求出相遇时间以及位置，取答案最大的时间和位置即可。

　　注意事项:

　　注意细节

　　#include

　　using namespace std;

　　int X[1010],Y[1010],vx[1010],vy[1010];

　　int mx=0;

　　int n;

　　void f(int X[],int vx[])

　　{

　　for(int i=1;i

　　{

　　unordered_map

　　int cnt=1;

　　for(int j=i+1;j<=n;j++)

　　{

　　if(vx[i]==vx[j])

　　{

　　if(X[i]==X[j])

　　cnt++;

　　mx=max(cnt,mx);

　　continue;

　　}

　　int dx=X[i]-X[j],dv=vx[j]-vx[i];

　　int t=dx/dv;

　　if(dx%dv||t<0)   continue;

　　m[t]++;

　　mx=max(mx,m[t]+cnt);

　　}

　　}

　　}

　　int main()

　　{

　　cin>>n;

　　for(int i=1;i<=n;i++)

　　{

　　int v;

　　char d;

　　cin>>X[i]>>Y[i]>>v>>d;

　　if(d=='R')

　　vx[i]=v;

　　if(d=='L')

　　vx[i]=-v;

　　if(d=='U')

　　vy[i]=v;

　　if(d=='D')

　　vy[i]=-v;

　　}

　　f(X,vx);

　　f(Y,vy);

　　cout<

　　return 0;

　　}