[白俊-11509]対気球

15337 ワード
greedy kotlin テキストリンク
質問リンク
初回試行(タイムアウト)
  • 提出番号:39431031
  • 最も簡単な方法-二重繰り返し文ですが、当然タイムアウトします.
    • 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回目の試み(成功)
  • 提出番号:39431375
  • 最悪の時間複雑度はまだO(N^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回目の試み(成功)
  • 提出番号: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 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()
}

    アノテーションコードのない開発者の作成に力を入れています.
    意図不明な(理解できない)コードがあれば、ご自由にお返事ください.本当にありがとうございます.
    内部クラスとは?Static Nested ClassとInner Classの違い.
    Android Handlerメカニズムバリアメッセージ(同期バリア)