#24182: 遞迴分治


hshua (hshua)

School : 新北市立林口高級中學
ID : 52506
IP address : [220.133.124.236]
Last Login :
2021-09-04 07:38:27
f638. 支點切割 -- APCS201802程式實作題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