[백준 10868 - Kotlin] 최솟값
15656 단어 SegmentTreekotlinSegmentTree
import java.io.BufferedReader
import java.io.BufferedWriter
import kotlin.math.min
import kotlin.math.pow
private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var input: MutableList<Int>
private lateinit var segTree: Array<Int>
fun main() {
bufferedReader = System.`in`.bufferedReader()
bufferedWriter = System.out.bufferedWriter()
// 1. get n, m
val (n, m) = bufferedReader
.readLine()
.split(" ")
.map { it.toInt() }
// 2. get input
input = mutableListOf()
for (i in 0 until n) {
input.add(bufferedReader.readLine().toInt())
}
// 3. construct segTree
val segTreeSize = getSegTreeSize(n)
segTree = Array(2 * segTreeSize - 1) { Int.MAX_VALUE }
constructSegTree(0, n - 1, 0)
// 4. get (a, b)
for (i in 0 until m) {
val (a, b) = bufferedReader
.readLine()
.split(" ")
.map { it.toInt() }
val answer = rangeMinQuery(a - 1, b - 1, 0, n - 1, 0)
bufferedWriter.write("$answer\n")
}
bufferedReader.close()
bufferedWriter.close()
}
fun getSegTreeSize(n: Int): Int {
var exponent = 1.0
while (n > 2.0.pow(exponent)) {
exponent++
}
return 2.0.pow(exponent).toInt()
}
fun constructSegTree(low: Int, high: Int, pos: Int) {
if (low == high) {
segTree[pos] = input[low]
return
}
val mid = (low + high) / 2
constructSegTree(low, mid, 2 * pos + 1)
constructSegTree(mid + 1, high, 2 * pos + 2)
segTree[pos] = min(segTree[2 * pos + 1], segTree[2 * pos + 2])
}
fun rangeMinQuery(qLow: Int, qHigh: Int, low: Int, high: Int, pos: Int): Int {
if (qLow <= low && qHigh >= high) return segTree[pos]
if (qLow > high || qHigh < low) return Int.MAX_VALUE
val mid = (low + high) / 2
return min(
rangeMinQuery(qLow, qHigh, low, mid, 2 * pos + 1),
rangeMinQuery(qLow, qHigh, mid + 1, high, 2 * pos + 2)
)
}
Author And Source
이 문제에 관하여([백준 10868 - Kotlin] 최솟값), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-10868-Kotlin-최솟값저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)