#29978: 比解答投影片更快的O(logn^2) 解找cost只要O(1)!!!
shaogan10555015@gmail.com
(少干)
學校
:
不指定學校
編號 : 126019
來源 : [49.215.37.242]
最後登入時間 ：
2023-03-21 00:55:20
a[]存角色等級
a[]小到大排序
sa[]存前綴和
sa2[]存平方前綴和(sa2[1]=a[0]^2+a[1]^2)
二分搜找U
對於每次遞迴
idx為a[]中第一個小於等於U的引索 或 n-1
《O(1)求cost》
cost=(idx+1)*U*U-2*U*sa[idx]+sa2[idx]
#29979: Re:比解答投影片更快的O(logn^2) 解找cost只要O(1)!!!
shaogan10555015@gmail.com
(少干)
學校
:
不指定學校
編號 : 126019
來源 : [49.215.37.242]
最後登入時間 ：
2023-03-21 00:55:20
由西格瑪公式推倒
#29982: Re:比解答投影片更快的O(logn^2) 解找cost只要O(1)!!!
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
由西格瑪公式推倒
我賽中是這樣寫的，但似乎會被卡，我subtask 1跟3(70分)有拿到，但subtask 2(30分)WA，我也不知道是甚麼測茲卡我，特判一下就被我拿滿囉(N<=100就爆搜)