作者xiefengan (阿噗拉)
看板Prob_Solve
標題[問題] ZJ d847: 2D rank finding problem
時間Wed Oct 17 00:50:14 2018
這學期學校在學演算法
剛好教到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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1539708624.A.053.html
1F：推 FRAXIS: 題目到底是什麼？？ 10/17 11:05
2F：→ c910335: 乍看之下你的程式碼是常數很大的 O(n^2) 10/17 16:19
3F：→ c910335: 兩個兩個比對硬做的 O(n^2) 比你寫的簡單而且更快 10/17 16:20
4F：→ c910335: 思路大致上是可行的 10/17 16:24
5F：→ c910335: 但是你有想過你的實作還是比較了每一對 甚至比較了更多次 10/17 16:25
6F：→ c910335: 用這麼複雜的實作比暴力還慢有什麼意義嗎 10/17 16:25