Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

处理曼哈顿距离时的扫描

Posted by yc5_yc at 2012-07-31 14:11:25 on Problem 3212

看了fanhqme的雁过留声后很容易想到怎样将它转化为曼哈顿距离
但处理曼哈顿距离的“线性扫描”我却不会
其实是这样的：
假设一个线段

__ ______ _ ___ __ ____ __ __ __

中间的空隙为点，我们要统计每个点与所有点的距离和
我们分两次统计，一次统计前面的，另一次是后面的

第一个很容易

__
__ ______ _ ___ __ ____ __ __ __

第二个我们尝试加上两个

   ______  
__ ______
__ ______ _ ___ __ ____ __ __ __

没有问题

那么第三个我们再加上三个？

          _
   ______ _ 
__ ______ _
__ ______ _ ___ __ ____ __ __ __

非常成功，那么我们就可以知道:
到达第N个点的长度和就是前N-1个点的长度和加上N*第N条线段的长

                              __   
                           __ __
                        __ __ __
                   ____ __ __ __
                __ ____ __ __ __
            ___ __ ____ __ __ __
          _ ___ __ ____ __ __ __
   ______ _ ___ __ ____ __ __ __
__ ______ _ ___ __ ____ __ __ __
__ ______ _ ___ __ ____ __ __ __