[AtCoder] AtCoder Beginner Contest 320 E. Somen Nagashi

문제풀이

1. 우선 순위 큐와 TreeSet을 사용하여 현재 시간에 가장 앞 열에 있는 사람을 구한다.

---

주의사항

---

소요시간

12분

---

package AtCoder.ProblemList.Difficulty800_1199.SomenNagashi

import java.util.PriorityQueue
import java.util.TreeSet

fun main() {
    val (N, M) = readln().trim().split(" ").map(String::toInt)
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    val result = LongArray(N)
    val set = TreeSet((0 until N).toSet())
    repeat(M) {
        val (T, W, S) = readln().trim().split(" ").map(String::toInt)
        while (pq.isNotEmpty() && T >= pq.first().second) set.add(pq.poll().first)
        if (set.isNotEmpty()) {
            val idx = set.first()
            set.remove(idx)
            result[idx] += W.toLong()
            pq.add(idx to (T + S))
        }
    }
    println(result.joinToString("\n"))
}

---

문제링크

https://atcoder.jp/contests/abc320/tasks/abc320_e