洛谷同文链接

P3843 [TJOI2007] 迷路 题解

题目传送门

14 分错因：

有很大可能是看错了题， $d$ 是每个任务总共要走的路程，而两个人每秒只能走一个单位。

思路

因为小 A 和小 B 的运动轨迹是周期性的，会循环，因此我们只需要 $\gcd$ 一下，求出最小公倍数，然后暴力枚举，用两点之间距离公式来计算所有时刻的距离，最后取 $\min$ 并输出就可以了。

两点距离公式：
$\sqrt{(x_1−x_2)×(x_1−x_2)+(y_1−y_2)×(y_1−y_2)}$。

剩下问题见于代码。

#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;//完美结束
}

完美结束。