题解：P2963 [USACO09NOV] Cow Rescue G

Tracy_Loght · 2024-12-06 15:00:25 · 题解

题目大意：

求多点在三角字形塔中的距离。

分析：

找规律，如图：

（你看看我多好，还不点个赞）

有一个容易得到的结论:

比如我们要从 6，6 走到 4 行的任意一个位置，则一定可以用三到四步之间走到。

映射到所有的情况，从 a，b 到 x，y 且 (a > x)，则 y 如果在区间 [b - ( a - x ) \times 2，b] 内只需要 ( a - x ) \times 2 或 ( a - x ) \times 2 +1 次破壁，具体看奇偶性。

如果不在这个区间内呢？

答案是两点之间，直线最短，计算区间里目标的最短距离即可（直线上不需要说了吧）。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,s,x,y,jl=99999999;
long long mx,my;
int dpzc_jf(int a,int b,int x,int y){
    int l,r,p=(a-x)*2;
    if(b%2==1) {l=b-p;r=b;}
    else {l=(b+1)-p;p--;r=b-1;}
    if(l<=0) l=1; if(r>x*2-1) r=x*2-1;
    if(l<=y&&y<=r) return y%2==1?p:p+1;
    else if(y>r) return p+y-r;else return p+l-y;
}
int main(){
    ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0); 
    cin>>n>>m>>x>>y;
    while(m--){
        long long a,b,as;cin>>a>>b;
        if(a>x) as=dpzc_jf(a,b,x,y);
        else as=dpzc_jf(x,y,a,b);
        if(as+1<jl) mx=a,my=b;
        jl=min(jl,as+1);
    }
    cout<<mx<<" "<<my<<"\n";
    cout<<jl;
    return 0;
}