→ yam276: 今天好難喔 06/21 21:43
→ Rushia: 其實用到兩種演算法的題目應該都偏hard 06/21 21:44
→ Rushia: Medium一般都是確定要用哪個演算法之後套上去就會過了 06/21 21:45
推 sustainer123: 大師 06/21 21:49
※ 引述《oin1104 (是oin的說)》之銘言：
: 題目 :
: 給你一串陣列customers
: 是在第 i 分鐘 會來的customers[i] 個客人
: 還有grumpy
: 是在第 i 分鐘 1會生氣 或0不會生氣的老闆
: 老闆生氣的話客人就哭哭跑掉
: 沒生氣的話客人就可以買東西
: 你可以痛扁老闆一次
: 讓他不要生氣持續minutes 分鐘
: 請問最多有多少客人可以買到東西
思路：
1.第一眼看到題目感覺是dp => 想不到 => 感覺是前綴和 => 寫起來卡卡怪怪的 =>
畫圖 => 感覺可以把 grumpy[i] == 0 的加起來然後再加上最長的 grumpy[i] == 1
對應的customers子陣列和
2.上面兩步就是貪婪+滑動窗口 寫出來一次就AC了
java code
--------------------------------------------------
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int n = customers.length;
int res = 0;
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) {
res += customers[i];
}
}
int curr_loss = 0;
int max_loss = 0;
for (int i = 0; i < n; i++) {
curr_loss += grumpy[i] == 1 ? customers[i] : 0;
if (i >= minutes) {
curr_loss -= grumpy[i - minutes] == 1 ? customers[i -
minutes] : 0;
}
max_loss = Math.max(max_loss, curr_loss);
}
return res + max_loss;
}
}
--------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718977319.A.E19.html
※ 編輯: Rushia (122.100.73.13 臺灣), 06/21/2024 21:42:51