※ 引述《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