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

[xiefengan (阿噗拉)]

這學期學校在學演算法
剛好教到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
推 FRAXIS: 題目到底是什麼？？
→ c910335: 乍看之下你的程式碼是常數很大的 O(n^2)
→ c910335: 兩個兩個比對硬做的 O(n^2) 比你寫的簡單而且更快
→ c910335: 思路大致上是可行的
→ c910335: 但是你有想過你的實作還是比較了每一對 甚至比較了更多次
→ c910335: 用這麼複雜的實作比暴力還慢有什麼意義嗎