PTT數位生活區 / C_and_CPP (C/C++)

Fw: [問題] 請教 zerojudge c260 的想法 (已解決)

看板C_and_CPP (C/C++)作者 (萌新冒險者)時間7年前 (2019/01/31 00:06), 編輯推噓3(3推 0噓 17→)
留言20則, 4人參與, 7年前最新討論串1/1
※ [本文轉錄自 Prob_Solve 看板 #1SKMSVJI ] 作者: vincent97198 (萌新冒險者) 看板: Prob_Solve 標題: [問題] 請教 zerojudge c260 的想法 時間: Wed Jan 30 16:58:05 2019 問題 https://zerojudge.tw/ShowProblem?problemid=c260 我的想法: 單調佇列找解 我的程式碼 https://ideone.com/A8PxXy 我的問題: 要用什麼方法才能找到全部的解呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.33.208.245 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1548838687.A.4D2.html ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: vincent97198 (1.175.218.216), 01/31/2019 00:06:27
→
01/31 00:09, 7年前 , 1F
補了程式碼應該不會被當成伸手文了吧
01/31 00:09, 1F
推
01/31 00:48, 7年前 , 2F
(a) 先把問題 reduce 到 「求平均值 > x 的 段數」
01/31 00:48, 2F
→
01/31 00:49, 7年前 , 3F
(b) 要求解 (a) ，我們可以把每個值都減掉 x，問題
01/31 00:49, 3F
→
01/31 00:49, 7年前 , 4F
就被 reduce 到「求平均值為正的段數」
01/31 00:49, 4F
→
01/31 00:49, 7年前 , 5F
接著由左到右枚舉蛋糕尾端，過程中用 set 維護
01/31 00:49, 5F
→
01/31 00:50, 7年前 , 6F
sums ，就能快速查詢有幾個蛋糕頭的位置合法
01/31 00:50, 6F
→
01/31 00:50, 7年前 , 7F
*維護 prefix sums
01/31 00:50, 7F
→
01/31 02:09, 7年前 , 8F
謝謝我懂了
01/31 02:09, 8F
推
01/31 12:34, 7年前 , 9F
這樣每次維護是O(n)？
01/31 12:34, 9F
→
01/31 14:11, 7年前 , 10F
對誒，這樣好像不能在時限內誒
01/31 14:11, 10F
→
01/31 16:45, 7年前 , 11F
對耶，C++的set沒辦法O(logN)查詢比x小的元素數量
01/31 16:45, 11F
→
01/31 16:46, 7年前 , 12F
那就把set改成 離散化 + fenwick tree 應該就可以了？
01/31 16:46, 12F
→
01/31 16:47, 7年前 , 13F
謝謝你的P幣
01/31 16:47, 13F
→
01/31 18:42, 7年前 , 14F
s大可以說得更詳細一點嗎?
01/31 18:42, 14F
→
01/31 22:06, 7年前 , 15F
01/31 22:06, 15F
推
02/01 15:19, 7年前 , 16F
每個數減掉平均上/下限 找in/decreasing pair數
02/01 15:19, 16F
→
02/01 15:19, 7年前 , 17F
這些pair就是不符合的
02/01 15:19, 17F
→
02/01 15:20, 7年前 , 18F
找pair數的方法可以從merge sort過程找
02/01 15:20, 18F
→
02/01 15:21, 7年前 , 19F
這邊的每個數=prefix sum的array(最前面補0)
02/01 15:21, 19F
→
02/01 15:24, 7年前 , 20F
有點描述錯誤 是所有數減完上/下限再做 prefix sum
02/01 15:24, 20F
‣ 更多 vincent97198 的文章
文章代碼(AID): #1SKSk5fI (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 vincent97198 的文章
文章代碼(AID): #1SKSk5fI (C_and_CPP)