Re: [問題] ZeroJudge-c216
看板Prob_Solve (計算數學 Problem Solving)作者GYLin (Lynx)時間5年前 (2019/04/02 20:45)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/3 (看更多)
大致策略:
1. 把途中所有累積加值都模100000, 原因很明顯
2. 當需要計算Sum[L,R]時, 其值為"不考慮爆掉的原本加總"扣掉100000*(區間內爆掉人數)
爆掉人數為: 區間內的Ai個數, 其值加上目前累積加值會超過100000的人們
要計算爆掉人數, 只要維護一個 Map[i][j] 就可以,
Map[i][j] 就是 陣列 1~i, 加上高度 j 會爆掉的人數,
若開普通陣列可能需要 100000*100000 的大小,
但實際上出現的詢問只會有 10^6 種,
所以先把詢問全部存起來後, 再針對會出現的詢問求出爆掉人數,
再回去把存起來的詢問解決即可.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.107.14
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1554209135.A.08E.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 2 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
