推 pandix: 大師 02/05 12:06
這次還行
https://i.imgur.com/fSiFtLV.png
1. Take Gifts From the Richest Pile
用一個 heap 來不斷取出最大值
不過因為 n, k <= 1000
所以其實可以不需要 heap 就是了
沒看到 floor 在那邊找到底有沒有一定是整數
第一題就花了八分鐘 = =
2. Count Vowel Strings in Ranges
建一個 prefix sum 陣列即可
3. House Robber IV
我用 binary search 解的
答案能夠 <= v 的條件是：
在只選那些 <= v 的人時能不能選出 >= k 個
不知道有沒有線性解就是了
4. Rearranging Fruits
首先每個數字的出現次數必須是偶數否則不可能
接著對各自陣列找出多出來的部份
假如多出來的部份分別是
A = a_1, a_2, ..., a_k
B = b_1, b_2, ..., b_k
則對於 A 而言，我們最後要讓個數一樣
所以最終一定是以下這種形式
換出 a_1, a_2...，a_k
換進 b_1, b_2, ..., b_k
換出及換進相等次數的 t_1, t_2, ...
對於固定好換出 (a_1, ..., t_1, t_2,...) 換進 (b_1, ..., t_1, t_2, ...)
而言，假如有 n 個數
最佳解一定是挑比較小的 n/2 個數分別配上比較大的 n/2 個數
因此最後的最佳解就會是
a_1, a_2, ..., a_k, b_1, b_2, ..., b_k
中最小的 k 個數，但可以用兩次 basket1 及 basket2 中的最小值代替
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675569694.A.C2A.html