PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 數列問題

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