×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
Problems
Submissions
Rank
Forum
Contest
Login
Register
New Thread
解題報告
#24182: 遞迴分治
hshua
(hshua)
School : 新北市立林口高級中學
ID : 52506
×
傳送站內訊息
To:
Subject:
Content:
IP address : [125.228.147.181]
Last Login :
2025-07-10 20:33:08
f638.
支點切割
--
APCS
201802
程式實作題
3
| From: [220.133.124.237] | Post Date : 2021-01-25 22:17
<演算思維>
遞迴 - 分治法,但 O(n^2) 會 TLE !
1. 求前輟和 pre[]
2. 求後啜和 rev[]
3. 對於區間 [L, R] 而言,求 L+1 ~ R-1 每一點左側距離 LA[] 與 右側距離 RA[]
LA[L] = RA[R] = 0;
for(int i=L+1; i<=R-1; i++) LA[i] = LA[i-1] + pre[i-1] - pre[L-1];
for(int i=R-1; i>=L+1; i--) RA[i] = RA[i+1] + rev[i+1] - rev[R+1];
4. 取第一個 abs(LA[i] - RA[i]) 最小值的作為 H行政中心點
5. 最後累加所有 H 中心點的結果
時間複雜度~ O(n)
ZeroJudge Forum