136 lines
2.1 KiB
Go
136 lines
2.1 KiB
Go
package main
|
|
|
|
type Queue interface {
|
|
Enqueue(value int)
|
|
Dequeue() int
|
|
Peek() int
|
|
IsEmpty() bool
|
|
}
|
|
|
|
type MonoDecQueue struct {
|
|
elements []int
|
|
}
|
|
|
|
func NewMonoDecQueue() *MonoDecQueue {
|
|
return &MonoDecQueue{elements: make([]int, 0)}
|
|
}
|
|
|
|
func (q *MonoDecQueue) Enqueue(value int) {
|
|
for !q.IsEmpty() && q.elements[len(q.elements)-1] < value {
|
|
q.elements = q.elements[:len(q.elements)-1]
|
|
}
|
|
q.elements = append(q.elements, value)
|
|
}
|
|
|
|
func (q *MonoDecQueue) Dequeue() int {
|
|
if q.IsEmpty() {
|
|
panic("queue is empty")
|
|
}
|
|
value := q.elements[0]
|
|
q.elements = q.elements[1:]
|
|
return value
|
|
}
|
|
|
|
func (q *MonoDecQueue) Peek() int {
|
|
if q.IsEmpty() {
|
|
panic("queue is empty")
|
|
}
|
|
return q.elements[0]
|
|
}
|
|
|
|
func (q *MonoDecQueue) IsEmpty() bool {
|
|
return len(q.elements) == 0
|
|
}
|
|
|
|
func MaximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
|
|
l := len(chargeTimes)
|
|
if l != len(runningCosts) {
|
|
return 0
|
|
}
|
|
|
|
j := 0
|
|
prevJ := -1
|
|
s := 0
|
|
maxRobots := 0
|
|
|
|
q := NewMonoDecQueue()
|
|
|
|
for i := 0; i < l; i++ {
|
|
|
|
if j < i {
|
|
j = i
|
|
}
|
|
|
|
for ; j < l; j++ {
|
|
num := j - i + 1
|
|
if prevJ != j {
|
|
s += runningCosts[j]
|
|
q.Enqueue(chargeTimes[j])
|
|
}
|
|
|
|
prevJ = j
|
|
if int64(s*num+q.Peek()) <= budget {
|
|
if maxRobots <= num {
|
|
maxRobots = num
|
|
}
|
|
} else {
|
|
break
|
|
}
|
|
}
|
|
|
|
if !q.IsEmpty() {
|
|
if q.Peek() == chargeTimes[i] {
|
|
q.Dequeue()
|
|
}
|
|
}
|
|
|
|
s -= runningCosts[i]
|
|
}
|
|
|
|
return maxRobots
|
|
}
|
|
|
|
func MaximumRobotsEx(chargeTimes []int, runningCosts []int, budget int64) int {
|
|
l := len(chargeTimes)
|
|
if l != len(runningCosts) {
|
|
return 0
|
|
}
|
|
|
|
prevCharges := make([]int, l)
|
|
prevCosts := make([]int, l)
|
|
maxWndRobots := make([]int, l+1)
|
|
|
|
maxRobots := 0
|
|
|
|
for wnd := 1; wnd <= l; wnd++ {
|
|
windows := l - wnd + 1
|
|
|
|
begin := 0
|
|
end := wnd - 1
|
|
w := 0
|
|
for w = 0; w < windows; w++ {
|
|
m := chargeTimes[end]
|
|
|
|
if m > prevCharges[w] {
|
|
prevCharges[w] = m
|
|
}
|
|
prevCosts[w] += runningCosts[end]
|
|
|
|
totalCost := int64(wnd*prevCosts[w] + prevCharges[w])
|
|
if totalCost <= budget {
|
|
maxRobots = wnd
|
|
}
|
|
|
|
begin++
|
|
end++
|
|
}
|
|
|
|
maxWndRobots[wnd] = maxRobots
|
|
if maxWndRobots[wnd] == maxWndRobots[wnd-1] {
|
|
break
|
|
}
|
|
}
|
|
|
|
return maxRobots
|
|
}
|