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

解题思路:

轨道炮：

看题找算法:

典型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<n;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<<mx;

    return 0;

}