作者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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1422697483.A.272.html
1F：推 guest2: 你效能分析的結論怪怪的,Q跟N範圍一樣 01/31 20:51
2F：→ guest2: 兩個方法都是O(N^2)吧 01/31 20:52
3F：→ guest2: hint: sum(A...B)=sum(1...B)-sum(1...A-1) 01/31 20:55
4F：→ williamd4112: 阿...看到hint突然好想撞牆...根本就不用方陣來存阿 01/31 22:24
5F：→ williamd4112: 只要花O(n)時間跑一次prefix sum就好............. 01/31 22:24
6F：推 guest2: 另外假設你得到每個人的分數score[1...Q] 01/31 23:11
7F：→ guest2: 從反方向處理會比你從正向用count數更快 01/31 23:14
8F：→ guest2: complexity會從O(QK)=>O(Q) 01/31 23:15
9F：→ guest2: 抱歉 應該是從O(Q^2)=>O(Q) 01/31 23:21
10F：→ williamd4112: 從反向可以做到O(Q)？！如果可希望能提示更多... 02/01 00:05
11F：→ aaaaajack: 先排序一遍找每個人的排位 02/01 02:29
12F：→ aaaaajack: 然後用fenwick tree倒著作回來應該可以做到O(QlogQ) 02/01 02:30
13F：→ aaaaajack: 又或者簡單一點用priority_queue維護最小k個數 02/01 02:37
14F：→ aaaaajack: 怎麼做到O(Q)我就比較沒概念了，一時之間沒想法 02/01 02:37
15F：推 guest2: 關鍵在於比後面k個人大 02/01 12:21
16F：推 guest2: 第Q-K到第Q個人一定不及格 02/01 12:23
17F：推 guest2: 第Q-K-1要及格要大於後面K個 02/01 12:26
18F：推 guest2: 從Q-K-1到1每個人都要大於後面第K小的 02/01 12:33
19F：推 guest2: 思考如何在新增一個元素進array的同時在O(1)時間找到第K小 02/01 12:40
20F：推 guest2: 當然你必須先花O(K)的時間找到你要的資訊 02/01 12:43
21F：推 guest2: 抱歉 aaaaa大是對的，應該是O(QlogQ) 02/01 14:13
22F：→ guest2: 用priority_queue維護最小k個數才對 02/01 14:14
24F：→ williamd4112: 但當時沒有想到說維護k個數字就好xd 02/01 14:52
25F：→ williamd4112: 但這段code還是re了...看來還得花一段時間來debug.. 02/01 14:53
26F：推 guest2: array大小可以動態改變??! 02/01 15:21
27F：→ williamd4112: 上面這段是因為用priority_queue跑RE...想說換個類 02/01 16:34
28F：→ williamd4112: 換成heap來做不知道會不會正確,結果還是re... 02/01 16:34
29F：→ williamd4112: 看了好久沒看出哪裡可能RE說... 02/01 16:35
30F：→ williamd4112: AC了,原來記憶體很吃緊,不能用long long 02/01 17:08
31F：→ williamd4112: 而seq[n]也是多開的空間,然後sums[n]應該改成sums[q 02/01 17:08
32F：→ williamd4112: 不過看Rank有人可以做到0.001 ... 02/01 17:11
33F：→ williamd4112: 我目前只能做到0.444... 02/01 17:11
34F：推 guest2: 原來 int seq[n]; 這種寫法合法啊...我還以為compiler會Er 02/01 18:59
35F：→ guest2: 要解記憶體大小RE的問題可以把變數丟到global變數啦 02/01 19:01
36F：→ guest2: 用long long並沒有錯，可能的範圍-100000000~100000000 02/01 19:02
37F：→ guest2: 本來就應該宣告成long long 02/01 19:03
38F：→ williamd4112: seq[n]那個寫法我記得以前上課時也是被告誡過... 02/01 21:38
39F：→ williamd4112: 不過後來compiler都會過就沒再去想了,我查看看 02/01 21:39
40F：推 FRAXIS: int seq[n]是C99的功能 找wiki的Variable-length array 02/01 22:22
41F：→ suhorng: C++ 的話就完全是 compiler extension 了 02/02 01:28
42F：推 lmr3796: C99的VLA跟終於可以for(int i;;)是我放下ansi c的關鍵XD 02/21 00:23