作者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/cn.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