→ yam276: 建議痛毆老闆 扁到他不敢對客人不敬 06/22 01:32
推 Furina: 大師 06/22 01:33
推 sustainer123: 改成老闆打遊戲比較符合本版狀況 06/22 01:33
→ sustainer123: 對不起對不起對不起 06/22 01:33
1052. Grumpy Bookstore Owner
兩個矩陣
customers:customers[i]代表第i分鐘來客數
grumpy:grumpy[i]代表店主在第i分鐘心情不好
當店主心情不好，就不能滿足客戶
店主可以連續minutes保持心情好
請問店主最多可以滿足幾個客人?
思路:
用sliding window紀錄連續minutes中有幾個店主心情不好時的來客數
取最多心情不好時的來客數
並且記錄所有店主心情好的時候的來客數
最後將這兩個值相加就是答案
golang code :
func maxSatisfied(customers []int, grumpy []int, minutes int) int {
n, sum, window, maxcus := len(customers), 0, 0, 0
for i := 0; i < minutes; i++ {
sum += (grumpy[i] ^ 1) * customers[i]
window += grumpy[i] * customers[i]
}
maxcus = window
for i := minutes; i < n; i++ {
sum += (grumpy[i] ^ 1) * customers[i]
window += grumpy[i] * customers[i]
window -= grumpy[i-minutes] * customers[i-minutes]
maxcus = max(maxcus, window)
}
return maxcus + sum
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.212.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718991076.A.7F0.html