Re: [問題] 程式作業加分題
看板Prob_Solve (計算數學 Problem Solving)作者pttworld (批踢踢世界)時間6年前 (2018/10/26 14:53)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1540536832.A.878.html
※ 編輯: pttworld (223.136.15.86), 10/26/2018 14:55:13
推
10/26 17:32,
6年前
, 1F
10/26 17:32, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
