推 pandix: 大師 12/25 12:05
→ NTHUlagka: 大師 12/25 12:33
這場打爛了
https://i.imgur.com/zQkxwTz.png
卡在第三題，卡到還先跑去寫第四題
明明昨天才寫過一題二分搜 :(
1. Shortest Distance to Target String in a Circular Array
遇到是 target 的就看他和 startIndex 的距離能不能更新最佳解
2. Take K of Each Character From Left and Right
這題我也小卡，最後把頭尾至少各取 k 個這個條件
改成取一個 sliding window 且各字母取的數目至少要留 k 個給其他人
兩個條件是等價的
不知道有沒有比較好的寫法
3. Maximum Tastiness of Candy Basket
我卡了，卡爆，但完全不應該卡的
總之就是對 tastiness 做二分搜
4. Number of Great Partitions
兩個 partition 都要 >= k
因為 k <= 1000，所以可以用 DP 算出 >= k 的子集數目
再扣掉 < k 的子集數目就可以了（因為兩個互補）
忘了 sum - k >= k 這個條件吃到 penalty
這場不太順
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671940912.A.4C4.html