题解：P3843 [TJOI2007] 迷路
joshua0729
·
·
题解
P3843 [TJOI2007] 迷路 题解
题目传送门
14 分错因：
有很大可能是看错了题， d 是每个任务总共要走的路程，而两个人每秒只能走一个单位。
思路
因为小 A 和小 B 的运动轨迹是周期性的，会循环，因此我们只需要 \gcd 一下，求出最小公倍数，然后暴力枚举，用两点之间距离公式来计算所有时刻的距离，最后取 \min 并输出就可以了。
两点距离公式：
剩下问题见于代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);//求最大公约数
}
int lcm(int a,int b){
return a/gcd(a,b)*b;//调用gcd，求最小公倍数
}
void path_read(vector<int>&x_coords,vector<int>&y_coords){//读取轨道坐标
int sx,sy,m;
cin>>sx>>sy>>m;//起始点坐标，指令条数
x_coords.clear();//清空坐标
y_coords.clear();
int current_x=sx;
int current_y=sy;
for(int i=0;i<m;++i){//m条指令
int d;
char c;
cin>>d>>c;
int s=abs(d);
int dir_x=0,dir_y=0;
if(c=='X'){
dir_x=d>0?1:-1;
}
else{
dir_y=d>0?1:-1;
}
for(int j=0;j<s;++j){//s步
current_x+=dir_x;
current_y+=dir_y;
x_coords.push_back(current_x);//将坐标存入
y_coords.push_back(current_y);
}
}
}
int main(){
vector<int>a_x,a_y,b_x,b_y;
path_read(a_x,a_y);//读取小A的轨道
path_read(b_x,b_y);//读取小B的轨道
int ta=a_x.size();//小A的轨道长度
int tb=b_x.size();//小B的轨道长度
if(ta==0||tb==0){//特判，如果轨道长度为0，直接输出0.00
printf("0.00\n");
return 0;
}
int L=lcm(ta,tb);//计算最小公倍数
double min_dist=1e18;//初始化最小距离为1e18
for(int t=0;t<L;++t){//枚举每个时刻
int a_idx=t%ta;//小A的当前位置
int b_idx=t%tb;//小B的当前位置
int dx=a_x[a_idx]-b_x[b_idx];//下一个x坐标
int dy=a_y[a_idx]-b_y[b_idx];//下一个y坐标
double dist=sqrt(dx*dx+dy*dy);//计算距离
min_dist=min(min_dist,dist);//更新最小距离
}
printf("%.2f\n",min_dist);//输出最小距离，保留两位小数，没得说
return 0;//完美结束
}
```
完美结束。