[問題] uva 12532 WA

看板C_and_CPP (C/C++)作者 (fakewen)時間12年前 (2013/10/05 17:07), 編輯推噓2(207)
留言9則, 3人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) C++ 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question): WA 餵入的資料(Input): 預期的正確結果(Expected Output): 錯誤結果(Wrong Output): 程式碼(Code):(請善用置底文網頁, 記得排版) http://codepad.org/sxkTiYxY 補充說明(Supplement): 我參照了morris大大的解答 自己寫了一份 自己的測試都OK 可是就是WA 實在是不知道哪裡出了問題... 會是輸出格式嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.42.103.240

10/06 12:59, , 1F
我來解答一下好了,差別在於 build() 的第一行初始
10/06 12:59, 1F

10/06 13:00, , 2F
劃分成兩區段的遞迴中,右側可能會超過邊界。
10/06 13:00, 2F

10/06 13:01, , 3F
在計算答案上,我仍然使用超過邊界的部分。由於有初始
10/06 13:01, 3F

10/06 13:01, , 4F
化,所以不影響答案計算結果。
10/06 13:01, 4F

10/06 18:22, , 5F
可以問Morris AC時間嗎? 這題我寫太慢花了一秒整。
10/06 18:22, 5F

10/06 21:46, , 6F
204 ms,還有可以優化的地方,輸出先壓成 char array 最
10/06 21:46, 6F

10/06 21:46, , 7F
最後在執行一次輸出,減少 function 呼叫。
10/06 21:46, 7F

10/06 21:50, , 8F
binary indexed tree 的解法說不定有機會比較快。
10/06 21:50, 8F

10/07 13:44, , 9F
Morris大大 在什麼情況會超界阿 我沒看出來
10/07 13:44, 9F
文章代碼(AID): #1IJzRZJ3 (C_and_CPP)
文章代碼(AID): #1IJzRZJ3 (C_and_CPP)