[白俊-11509]対気球


質問リンク
初回試行(タイムアウト)
  • 提出番号: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()
    }

    アノテーションコードのない開発者の作成に力を入れています.
    意図不明な(理解できない)コードがあれば、ご自由にお返事ください.本当にありがとうございます.