Re: [討論] GCJ結束了我要伸解法～
看板Prob_Solve (計算數學 Problem Solving)作者yyc1217 (somo)時間16年前 (2008/07/29 18:57)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/6 (看更多)
※ 引述《scan33scan33 (亨利喵)》之銘言：
: 這裡好像很多人在比，所以想問問看
: 解法，那我先就我知道的拋磚引玉吧！
: 題目在：
: http://code.google.com/codejam/contest
: 防雷頁
: 1a.Greedy
: 最大配最小就對了。
: 我也不知道怎麼對的，有誰要說明一下嗎？
: 時間複雜度：O(n lg n) (sorting)
原文恕刪
我認為這題並不是Greedy
不過的確是最大配最小
我的解法如下：
1.將第一個向量的值由大排到小 O（nlgn）
將第二個向量的值由小排到大 O（nlgn）
（一、二亦可顛倒）
2.求兩個向量的scalar product，所得的數即為所求 O（n）
即求X1Y1+X2Y2+...+XnYn
因此時間複雜度為O（nlgn）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.41.7
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
