P8695 [蓝桥杯 2019 国 AC] 轨道炮 题解
wuhan1234
·
·
题解
1. 编程思路。
由于题目中给定的点的个数 N 不超过 1000，数据规模不大，因此采用简单的暴力枚举可以解决本问题。
先定义 4 个数组 X、Y、vx 和 vy 分别保存每个敌方单位的位置坐标 (X_i,Y_i) 以及其在 X 轴正方向和 Y 轴正方向上的速度。在输入时预处理后保存。
以输入样例的 4 个敌方单位为例，输入预处理后，4 个数组相应数组元素的值可列举如下：
$X[2]=0, Y[2]=10, vx[1]=1, vy[1]=0
$X[4]=2, Y[4]=3, vx[4]=-2, vy[4]=0$ （向左为 X 轴负方向）
枚举的具体做法如下：
在 $N$ 个敌方单位中依次选择某个敌方单位作为基准点，设编号为 $i$，在其他的 $N-1$ 个敌方单位中统计有多少个单位与基准点同列（X 坐标相同）或同行（Y 坐标相同）。下面以同列的统计进行说明。
与基准点 $i$ 同列的某个敌方单位 $j$ 的情况分为两种：
1）$X_i$ 与 $X_j$ 相同，$vx_i$ 也与 $vx_j$ 相同，这样它们任何时刻都同列，将这样的单位的个数记录到变量 $cnt$ 中。当然，若 $vx_i$ 与 $vx_j$ 相同，但 $X_i$ 与 $X_j$ 不相同，这样的两个单位永远不可能同列，直接忽略掉。
2）$vx_i$ 与 $vx_j$ 不相同。计算这两个单位可能的同列时刻。计算方法为距离差除以速度差。即
$$t=\frac{X_i-Xj}{vx_i-vy_j}$$
计算后，若 $t$ 不小于 $0$ 并且距离差能整除速度差（相当于 $t$ 确实为整数时刻），则相应的数组元素 $h[t]$ 加 $1$，表示在 $t$ 时刻与基准点同列的单位多了 $1$ 个。
找出这两者同列点数和的最大值就是某时刻与基准点同列的最多单位。
每个点作为基准点所求得同列点数的最大值就是激光炮在一列上能消灭的最多敌方单位。
同理，可以求得激光炮在一行上（同 Y 坐标）能消灭的最多敌方单位。
取二者的最大值就是所求的答案。
## 2. 源程序。
```c
#include <stdio.h>
#include <string.h>
int ans;
int h[2000005]; // h[i]保存 i 时刻与给定点同X的点的个数
void calc(int X[],int vx[],int n)
{
int i,j;
for (i=1;i<=n;i++) // 对每个点进行枚举，看有多少个点在某时刻与其同列（同X坐标）
{
memset(h,0,sizeof(h));
int cnt=1;
for (j=1;j<=n;j++)
{
if (j==i) continue;
if (vx[i]==vx[j])
{
if (X[i]==X[j]) // 同初始X坐标同速度，任何时刻同X
cnt++;
if (ans<cnt) ans=cnt;
continue;
}
int dx=X[i]-X[j]; // 两个点的距离差
int dv=vx[j]-vx[i]; // 两个点的速度差
int t=dx/dv; // 两个点相遇的时间
if (dx%dv || t<0) continue;
h[t]++; // 在 t 时刻到达同X的点数加1
if (ans<h[t]+cnt) ans=h[t]+cnt;
}
}
}
int main()
{
int n;
scanf("%d",&n);
int X[1010],Y[1010],vx[1010]={0},vy[1010]={0};
for (int i=1;i<=n;i++)
{
int v;
char d[3];
scanf("%d%d%d%s",&X[i],&Y[i],&v,d);
switch (d[0])
{
case 'R': vx[i]=v; break;
case 'L': vx[i]=-v; break;
case 'U': vy[i]=v; break;
case 'D': vy[i]=-v; break;
}
}
ans=0;
calc(X,vx,n);
calc(Y,vy,n);
printf("%d\n",ans);
return 0;
}
```