討論串(共6篇) - [討論] GCJ結束了我要伸解法～ - 看板Prob_Solve

看板 [ Prob_Solve ]

討論串[討論] GCJ結束了我要伸解法～

共 6 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

[討論] GCJ結束了我要伸解法～

推噓0(0推 )留言0則，0人參與作者scan33scan33 (亨利喵)時間16年前 (2008/07/27 23:54)資訊

內容預覽:

這裡好像很多人在比，所以想問問看. 解法，那我先就我知道的拋磚引玉吧！. 題目在：. http://code.google.com/codejam/contest. 防雷頁. 1a.Greedy. 最大配最小就對了。. 我也不知道怎麼對的，有誰要說明一下嗎？. 時間複雜度：O(n lg n) (so

(還有1323個字)

Re: [討論] GCJ結束了我要伸解法～

推噓1(1推 )留言2則，0人參與作者Lucemia (生の直感、死の予感)時間16年前 (2008/07/28 23:41)資訊

內容預覽:

就我知道的部份講一下. 這個解法也是我從其他人聽來的線索中拼湊出來的. 不確定是否就是最佳解. 1. 假設 3 + 5^.5 = X ==> X^2 = 6X -4. 由此可以導出遞迴關析式 X^n = 6X^(n-1) - 4X^(n-2). 但不能直接由此式算出X, X^2後跑迴圈去解. 因為

(還有584個字)

Re: [討論] GCJ結束了我要伸解法～

推噓0(0推 )留言0則，0人參與作者yyc1217 (somo)時間16年前 (2008/07/29 18:57)資訊

內容預覽:

原文恕刪. 我認為這題並不是Greedy. 不過的確是最大配最小. 我的解法如下：. 1.將第一個向量的值由大排到小 O（nlgn）. 將第二個向量的值由小排到大 O（nlgn）. （一、二亦可顛倒）. 2.求兩個向量的scalar product，所得的數即為所求 O（n）. 即求X1Y1+X2Y

Re: [討論] GCJ結束了我要伸解法～

推噓3(3推 )留言3則，0人參與作者yoco315 (眠月)時間16年前 (2008/07/29 19:57)資訊

內容預覽:

我可以問一下證明嗎. 雖然到處看到都是這個解答. 不過我不是很懂為什麼這樣 work. --. To iterate is human, to recurse is divine.. 遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch. --. ※ 發信站: 批踢踢實業坊(ptt.

Re: [討論] GCJ結束了我要伸解法～

推噓1(1推 )留言1則，0人參與作者Lucemia (生の直感、死の予感)時間16年前 (2008/07/29 20:36)資訊

內容預覽:

假設 vector1是 (a1,a2,... an),vector2 是 (b1, b2,... bn). n = 2時很好證:. n = k 時. 假設最大配最小解法不為最好,. 則存在一組向量為最好. 其中至少存在一組 i, j <= n. 滿足ai < aj, bi < bj. 此組向量內積為

(還有125個字)

首頁

尾頁