作者pttworld (批踢踢世界)
看板Prob_Solve
标题Re: [问题] 程式作业加分题
时间Fri Oct 26 14:53:50 2018
※ 引述《aaaa11140 (Jimmy)》之铭言：
: 这是一个程式作业的加分题，
: 对於平面上两点A,B，d(A,B)表示从A到B的最短时间，
: 而移动的方式包括knight moving的8种以及上下左右一次一格，
: knight moving一次需时2秒，上下左右则是1秒。
: e.g.
: d((0,0),(2,2))=3
: 题目给定N个点，求每个点与其他点的最短时间和，意即对於第i的点xi，求Σd(xi,xj),1<=j<=N。
: N最大为10^5，时间限制2秒，所以不可能用两个loop找任意两点时间，希望跟大家讨论。
: 现在的进度是d(A,B)可以用O(1)的时间得知，问题卡在找所有任意两点的方法。
: -----
: Sent from JPTT on my Samsung SM-N960F.
xy距离分为长边短边
z1=min(长边/2, 短边)
边1=长边-2*z1, 边2=短边-z1
z2=min(max(边1, 边2)/2, min(边1, 边2))
边a=max(边1, 边2)-2*z2, 边b=min(边1, 边2)-z2
答案等於2*z1+2*z2+边a+边b秒
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.136.15.86
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1540536832.A.878.html
※ 编辑: pttworld (223.136.15.86), 10/26/2018 14:55:13
1F：推 aaaa11140: 这是d的公式，现在问题是没办法在时间内计算任两点距离 10/26 17:32