1878: [SDOI2009]HH的项链
2879: [Noi2012]美食节

1772: [Usaco2009 Nov]rescue 拯救奶牛貝希

高橋直樹 posted @ 2013年3月31日 14:56 in BZOJ with tags bzoj usaco , 1118 阅读

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);
}

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter