#34184: 解題報告


dfd8282@gmail.com (fishhh)

School : 嘉義市私立嘉華高級中學
ID : 99760
IP address : [163.27.13.253]
Last Login :
2024-05-23 11:00:10
f816. TOI_y21m4_a02Youtube -- toi練習賽2021年4月潛力組 | From: [163.27.13.253] | Post Date : 2023-03-04 10:04

我的做法就是前綴和 + 二分搜 + 差分

對 d 做前綴和,對於一個 v_i 一定會有一個被刪掉的時候 它在 被加入~被刪掉(被扣到小於0) 這段期間,一定會被扣掉這段期間的所有 d

所以我把它變成差分的形式 在我把這個數加入的時候,記錄一個 cnt_j 代表目前在算到 j 的時候所有不小於 0 且大於 d_j 的數 (就可以直接扣掉 cnt_j * d_j)

那如果目前這個數介於 0~d_j 之間呢 那麼這個數對於 ans_j的貢獻就直接是 0 就好 但不是每一個 v_i 扣到最後都會剛剛好是 0

所以要在差分那邊動一點手腳 直接在差分的時候直接扣掉就好(程式第31行)。

我覺得我國文不好 或許直接看程式會比較好理解XD

程式碼:

https://hackmd.io/@fishhh/rkZ2G7ey2

 
ZeroJudge Forum