Untitled
unknown
kotlin
8 months ago
2.7 kB
2
Indexable
Never
import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.PriorityQueue fun main(args: Array<String>) { val reader = BufferedReader(InputStreamReader(System.`in`)) val writer = BufferedWriter(OutputStreamWriter(System.out)) val inp = reader.readLine().split(" ").map { it.toInt() } val N = inp[0] val K = inp[1] val W = inp[2] val renters = MutableList(K) { IntArray(2) } repeat(K) { renters[it] = reader.readLine().split(" ").map { it.toInt() }.toIntArray() } renters.sortByDescending { it[0] } var profit = 0 for (builbord in 1..N) { if (renters.isEmpty()) break for (day in 1..W) { if (renters.isEmpty()) break val renter = renters.first() val cost = renter[0] val weeksLeft = renter[1] if (weeksLeft > 0) { profit += cost renter[1] -= 1 } else { renters.removeAt(0) if (renters.isEmpty()) break val newRenter = renters.first() profit += newRenter[0] newRenter[1] -= 1 } } } writer.write("$profit\n") reader.close() writer.close() } /* N - количество билбордов K - количество рекламодателей W - количество недель Основная идея: Жадность тут проявляется не только в том, чтобы всегда брать как можно более дорогие объявления, но также брать как можно больше объявлений (!) 1'st builbord 2'nd builbord ... n'th builbord | | v v *--------* *--------* | h.max | | h.max | *--* *--* *--* *--* ... <- 1'st day | | | | *-* *-* *--------* *--------* | h.max | | h.max | *--* *--* *--* *--* ... <- 2'st day | | | | *-* *-* ... *--------* *--------* | h.max | | h.max | *--* *--* *--* *--* ... <- w'th day | | | | *-* *-* Heap: *---* | . | *---* | . | *---* | . | *---* ... *---* | . | *---* N=2 K=3 W=3 ---------------- *---* |3 0| |2 2| < |1 2| *---* week 1: - 3 + 2 week 2: - 3 + 1 week 3: - 2 + 1 week 1: (3, 2) *---* |3 2| |2 2| |1 2| *---* profit= 0 + 3 + 2 week 2: (3, 1) profit= 5 + 3 + 1 week 3: (2, 1) profit = 9 + 2 + 1 = 12 */
Leave a Comment