推 NTHUlagka: 心態有點炸 第一題吃太多penalty 哭了 03/19 00:01
→ shiliuye: 寶很厲害了 03/19 00:55
第一題是哪個白癡出的 = =
我在那看老半天受不了搬到最後再寫
https://i.imgur.com/r3oOZsZ.png
沒有 hard 的話沒進 30 分排名就不會好看
1. Distribute Money to Maximum Children
條件有夠多，當你在寫作文嗎 = =
比較重要的觀察是當剩下的人數 >= 2 時，一定可以弄成所有人都不是 4 的情況
所以只有 money < children 會失敗
然後注意
1) money 超過 children * 8 答案是 children - 1
2) money == (children - 1) * 8 + 4 時只能 children - 2
3) 其他情況都能 (money - children) / 7
2. Maximize Greatness of an Array
Two-pointer.
首先，考慮最小的那個數，假如是 nums[i]
則這個最小的數一定可以是最佳解（或是答案是 0）
因為不是的話和隨便一個 perm[j] > nums[j] 互換
因為 perm[j] > nums[j] >= nums[i] 所以還是最佳解
接著考慮大於 nums[i] 裡最小的那一個
他作為 perm[i] 也要是最佳解
同樣如果不是的話就互換，依然都會是合法的
所以只要先 sort 完之後
再用 two-pointer 對所有 i 以盡量小的 j > i 使 nums[j] > nums[i] 即可
注意配對過的不能重複用
3. Find Score of an Array After Marking All Elements
用 set S 存所有的 pair<int,int>{nums[i], i}
則 S.begin() 就是最小的那一個
接著把 {nums[i+1], i+1} 和 {nums[i-1], i-1} 也 erase 掉就好
4. Minimum Time to Repair Cars
標準的二分搜
只要寫出給定時間 t 時能不能造出 >= cars
然後對 t 做二分搜就好，因為 t 能的話 t + 1 也一定能
好像想不太到二分搜以外的作法
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679155218.A.E40.html