[伯俊10868-Kotlin]最高価格
15702 ワード
質問リンク セグメントツリーキャビティの画像
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)
)
}
Reference
この問題について([伯俊10868-Kotlin]最高価格), 我々は、より多くの情報をここで見つけました https://velog.io/@kldaji/백준-10868-Kotlin-최솟값テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol