-
Notifications
You must be signed in to change notification settings - Fork 320
/
ch-2.kt
43 lines (40 loc) · 1.15 KB
/
ch-2.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
fun travelexpenditure(costs: List<Int>, days0: List<Int>): Int {
val days = ArrayList(days0).sorted()
val validities = listOf(1, 7, 30)
var stack = ArrayDeque<Pair<Int, List<Int>>>()
stack.add(Pair(0, days))
var cheapest = days.size * costs[0]
while (stack.size > 0) {
val c = stack.removeFirst()
if (c.second.size == 0) {
if (c.first < cheapest) {
cheapest = c.first
}
} else {
if (c.first >= cheapest) {
continue
}
val start = c.second[0]
for (i in 0..2) {
val ed = start + validities[i] - 1
var dtd = c.second.filter{it > ed}
stack.add(Pair(c.first + costs[i], dtd))
}
}
}
return cheapest
}
fun main() {
if (travelexpenditure(listOf(2, 7, 25), listOf(1, 5, 6, 7, 9, 15)) == 11) {
print("Pass")
} else {
print("Fail")
}
print(" ")
if (travelexpenditure(listOf(2, 7, 25), listOf(1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31)) == 20) {
print("Pass")
} else {
print("Fail")
}
println("")
}