1772: [Usaco2009 Nov]rescue 拯救奶牛貝希
http://www.lydsy.com/JudgeOnline/problem.php?id=1772
RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
380234 | Liu_Ts | 1772 | Accepted | 884 kb | 20 ms | C++ | 618 B | 2013-03-30 15:10:53 |
题意
给定一个N行的三角形矩阵,如图
求一个点到另外几个给定的点的距离中,最短的距离。
题解
挺好玩的,重建三维坐标系
对于三角形(i,j)
x=i,y=(j+1)div 2,z=(i*2-1-j+1)div 2=i-j div 2
可以证明对于任意两个三角形,
他们的距离恰为|x1-x2|+|y1-y2|+|z1-z2|。
#include<cstring> #include<algorithm> #include<cstdio> #include<climits> using namespace std; const int N=10001; int X[N],Y[N],n,m,sx,sy,sz,ax,ay,d; int main() { int a,b,x,y,z; scanf("%d%d%d%d",&n,&m,&a,&b); //x=i,y=(j+1)div 2,z=i-j div 2; sx=a;sy=(b+1)/2;sz=a-b/2; d=INT_MAX; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); x=a;y=(b+1)/2;z=a-b/2; int tmp=abs(x-sx)+abs(y-sy)+abs(z-sz); if((tmp<d)||(tmp==d && ax>a)||(tmp==d && ax==a && ay>b)) ax=a,ay=b,d=tmp; } printf("%d %d\n",ax,ay); printf("%d\n",d+1); }