#45903: 解題報告


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [114.40.199.16]
最後登入時間 :
2025-04-26 21:55:13
o344. 超市掃貨 | From: [114.40.199.16] | 發表日期 : 2025-04-26 22:33

我的作法是 二分搜+sparse table。

可以再思考一下為啥可以用二分搜->哪裡來的單調性,想不出來再往下滑。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

因為對於從 i 開始的某一方向,min 這個函數會有單調性,所以對 i 的左右分別去做二分搜,搜到比 ary[i] 還要小的數字之前的前一個數,那就是最小值為 ary[i] 可以構成的最大美味度,所以只要對於每一個點進行兩次二分搜,並且搭配 sparse table 就可以了。(也可以用線段樹之類的資結,只是會多一個 log)

 
ZeroJudge Forum