› 看板 Prob_Solve 關於我們 聯絡資訊
作者williamd4112 (Williamd)
看板Prob_Solve
標題[問題] 數列問題
時間Sat Jan 31 17:44:40 2015
原始題目：(非作業) http://acm.cs.nthu.edu.tw/problem.php?hash=9c16f6606460d1543759fc966b9bb797# 簡單敘述一下題目： 給一串有n個數字的數列 以及q個[a,b]的區間 如果第i個區間之後有兩個點數總和小於第i個區間的區間,則得到A+的人加1 我的作法 求區間總和： (1)建立一個n*n的方陣來存 summap[1][2]: 從1 ~ 2的總和 summap[3][6]: 從3 ~ 6的總和 在讀取序列時一起進行, 所以花了(n)* (n+1) / 2的時間來進行 (2)讀到區間後線性加總 譬如讀取到2 6的區間, 就把數列中從[1] ~ [5]的元素加總 最差狀況每個區間都是[1, n]的話,需要進行n * q次 儲存： (1)list： 宣告一個struct 來紀錄 sum(區間的和), counter(判斷其後是否有兩個小於自己的sum的數量) 先把數列完整讀入後,建立一個list來存以上的結構 每讀入一組區間, 建立一個結構來存, 然後判斷讀入的這個結構對list中的元素的counter的貢獻 (如果conuter == 2則ans++, 之後把該元素從list中erase) (2)陣列： 建立兩個大小為n的陣列,分別存sum, counter 每讀取一個區間就掃一次sum陣列 如果sum[i] > sum_current_input則counter++ 如果counter == 2時, ans加1次(不會重複加, 因為只有counter < 2時才會遞增counter 結果： summap目前會RE , 還在找問題, 可是summap效能分析起來比線性求和還要差... 所以考慮往別的方向找答案 線性求和的方式搭配list, array都是TLE... 還有哪裡可以改進效能的嗎？ 求和的地方實在想不到其他優化的方法了... 有沒有辦法減少讀取一個區間後, 判斷對數列影響的時間呢？ 或是有其他方法？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.142.129.2 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1422697483.A.272.html
推 guest2: 你效能分析的結論怪怪的,Q跟N範圍一樣 01/31 20:51
→ guest2: 兩個方法都是O(N^2)吧 01/31 20:52
→ guest2: hint: sum(A...B)=sum(1...B)-sum(1...A-1) 01/31 20:55
→ williamd4112: 阿...看到hint突然好想撞牆...根本就不用方陣來存阿 01/31 22:24
→ williamd4112: 只要花O(n)時間跑一次prefix sum就好............. 01/31 22:24
推 guest2: 另外假設你得到每個人的分數score[1...Q] 01/31 23:11
→ guest2: 從反方向處理會比你從正向用count數更快 01/31 23:14
→ guest2: complexity會從O(QK)=>O(Q) 01/31 23:15
→ guest2: 抱歉 應該是從O(Q^2)=>O(Q) 01/31 23:21
→ williamd4112: 從反向可以做到O(Q)？！如果可希望能提示更多... 02/01 00:05
→ aaaaajack: 先排序一遍找每個人的排位 02/01 02:29
→ aaaaajack: 然後用fenwick tree倒著作回來應該可以做到O(QlogQ) 02/01 02:30
→ aaaaajack: 又或者簡單一點用priority_queue維護最小k個數 02/01 02:37
→ aaaaajack: 怎麼做到O(Q)我就比較沒概念了，一時之間沒想法 02/01 02:37
推 guest2: 關鍵在於比後面k個人大 02/01 12:21
推 guest2: 第Q-K到第Q個人一定不及格 02/01 12:23
推 guest2: 第Q-K-1要及格要大於後面K個 02/01 12:26
推 guest2: 從Q-K-1到1每個人都要大於後面第K小的 02/01 12:33
推 guest2: 思考如何在新增一個元素進array的同時在O(1)時間找到第K小 02/01 12:40
推 guest2: 當然你必須先花O(K)的時間找到你要的資訊 02/01 12:43
推 guest2: 抱歉 aaaaa大是對的，應該是O(QlogQ) 02/01 14:13
→ guest2: 用priority_queue維護最小k個數才對 02/01 14:14
→ williamd4112: http://pastebin.com/mJmwVgeD 昨天也是想到用pq來 02/01 14:52
→ williamd4112: 但當時沒有想到說維護k個數字就好xd 02/01 14:52
→ williamd4112: 但這段code還是re了...看來還得花一段時間來debug.. 02/01 14:53
推 guest2: array大小可以動態改變??! 02/01 15:21
→ williamd4112: 上面這段是因為用priority_queue跑RE...想說換個類 02/01 16:34
→ williamd4112: 換成heap來做不知道會不會正確,結果還是re... 02/01 16:34
→ williamd4112: 看了好久沒看出哪裡可能RE說... 02/01 16:35
→ williamd4112: AC了,原來記憶體很吃緊,不能用long long 02/01 17:08
→ williamd4112: 而seq[n]也是多開的空間,然後sums[n]應該改成sums[q 02/01 17:08
→ williamd4112: 不過看Rank有人可以做到0.001 ... 02/01 17:11
→ williamd4112: 我目前只能做到0.444... 02/01 17:11
推 guest2: 原來 int seq[n]; 這種寫法合法啊...我還以為compiler會Er 02/01 18:59
→ guest2: 要解記憶體大小RE的問題可以把變數丟到global變數啦 02/01 19:01
→ guest2: 用long long並沒有錯，可能的範圍-100000000~100000000 02/01 19:02
→ guest2: 本來就應該宣告成long long 02/01 19:03
→ williamd4112: seq[n]那個寫法我記得以前上課時也是被告誡過... 02/01 21:38
→ williamd4112: 不過後來compiler都會過就沒再去想了,我查看看 02/01 21:39
推 FRAXIS: int seq[n]是C99的功能 找wiki的Variable-length array 02/01 22:22
→ suhorng: C++ 的話就完全是 compiler extension 了 02/02 01:28
推 lmr3796: C99的VLA跟終於可以for(int i;;)是我放下ansi c的關鍵XD 02/21 00:23