Untitled

mail@pastecode.io avatar
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