作者yyc1217 (somo)
看板Prob_Solve
标题Re: [讨论] GCJ结束了我要伸解法～
时间Tue Jul 29 18:57:51 2008
※ 引述《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