[白俊-11509]対気球
質問リンク
初回試行(タイムアウト)提出番号:39431031 最も簡単な方法-二重繰り返し文ですが、当然タイムアウトします. 提出番号:39431375 最悪の時間複雑度はまだO(N^2)なのでタイムアウトが予想されますが、無理に成功したと思います. 提出番号:39431709 O(N)の時間的複雑さ. すべての高さの矢印にメモリを割り当て、風船が置かれている高さをキー値とし、その高さの矢印数をキー値とする問題を解決します.
アノテーションコードのない開発者の作成に力を入れています.
意図不明な(理解できない)コードがあれば、ご自由にお返事ください.本当にありがとうございます.
初回試行(タイムアウト)
fun main() {
val bufferedReader = System.`in`.bufferedReader()
val bufferedWriter = System.out.bufferedWriter()
val n = bufferedReader.readLine().toInt()
val h = bufferedReader.readLine().split(" ").map { it.toInt() }
val popped = Array(n) { false }
var answer =0
for (i in 0 until n) {
var arrow = h[i]
if (!popped[i]) {
popped[i] = true
arrow--
for (j in i + 1 until n) {
if (!popped[j] && arrow == h[j]) {
popped[j] = true
arrow--
}
}
answer++
}
}
bufferedWriter.write("$answer")
bufferedReader.close()
bufferedWriter.close()
}
2回目の試み(成功)fun main() {
val bufferedReader = System.`in`.bufferedReader()
val bufferedWriter = System.out.bufferedWriter()
val n = bufferedReader.readLine().toInt()
val h = bufferedReader.readLine().split(" ").map { it.toInt() }
val arrows = mutableListOf<Int>()
var answer = 0
for (i in 0 until n) {
if (arrows.contains(h[i] + 1)) {
arrows.remove(h[i] + 1)
} else answer++
arrows.add(h[i])
}
bufferedWriter.write("$answer")
bufferedReader.close()
bufferedWriter.close()
}
3回目の試み(成功)fun main() {
val bufferedReader = System.`in`.bufferedReader()
val bufferedWriter = System.out.bufferedWriter()
val n = bufferedReader.readLine().toInt()
val h = bufferedReader.readLine().split(" ").map { it.toInt() }
val arrows = Array(1_000_001) { 0 }
var answer = 0
for (i in 0 until n) {
if (arrows[h[i]] == 0) answer++
else arrows[h[i]]--
arrows[h[i] - 1]++
}
bufferedWriter.write("$answer")
bufferedReader.close()
bufferedWriter.close()
}
アノテーションコードのない開発者の作成に力を入れています.
意図不明な(理解できない)コードがあれば、ご自由にお返事ください.本当にありがとうございます.
Reference
この問題について([白俊-11509]対気球), 我々は、より多くの情報をここで見つけました https://velog.io/@kldaji/백준-11509-풍선-맞추기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol