PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] ZJ d847: 2D rank finding problem

看板Prob_Solve (計算數學 Problem Solving)作者 (阿噗拉)時間5年前 (2018/10/17 00:50), 編輯推噓1(1推 0噓 5→)
留言6則, 2人參與, 5年前最新討論串1/1
這學期學校在學演算法 剛好教到divide-and-conquer 老師出了一個2D Ranking的題目 學校方面的是寫完了 畢竟測資自己訂 小弟之前也有寫Online Judge的習慣 想說找個judge測看看結果不會過 以下為程式碼 https://pastebin.com/XcKRH9z8 我的思考方式是先對全部的資料以x做大小排序 然後遞迴 剩一個就不動作 兩個的話互比y值再看要不要swap(以y排序) 大於兩個就拿右邊遞迴的比左邊遞迴的資料(左邊x值已經小於右邊所以只需比y) 然後做Ranking (可能解釋的不太好) 目前丟上去遇到: 我的答案:4040 正確答案:4038 想請問我的思考方向正確嗎 還是程式碼有哪裡沒考慮周到的嗎 謝謝>< -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.230.27 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1539708624.A.053.html
推
10/17 11:05, 5年前 , 1F
題目到底是什麼？？
10/17 11:05, 1F
→
10/17 16:19, 5年前 , 2F
乍看之下你的程式碼是常數很大的 O(n^2)
10/17 16:19, 2F
→
10/17 16:20, 5年前 , 3F
兩個兩個比對硬做的 O(n^2) 比你寫的簡單而且更快
10/17 16:20, 3F
→
10/17 16:24, 5年前 , 4F
思路大致上是可行的
10/17 16:24, 4F
→
10/17 16:25, 5年前 , 5F
但是你有想過你的實作還是比較了每一對 甚至比較了更多次
10/17 16:25, 5F
→
10/17 16:25, 5年前 , 6F
用這麼複雜的實作比暴力還慢有什麼意義嗎
10/17 16:25, 6F
‣ 更多 xiefengan 的文章
文章代碼(AID): #1RnXRG1J (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 xiefengan 的文章
文章代碼(AID): #1RnXRG1J (Prob_Solve)