[白俊]1377号:バブルスーツ

5406 ワード
Sort kotlin テキストリンク
質問リンク
  • iの2番目の数字がiより小さいと判断した場合、数字を計算してheapで解決しようとしたが、タイムアウトが発生し、セグメントツリーでタイムアウト問題を解決しようとしたが、最終的には誤りの結果が得られ、仮定が誤りであることが認識された.
  • 問題の解決方法は思ったより簡単です.Buttle Sotは、昇順の場合、小数が大数より大きい場合、Iterationを行うたびにさらに進む事実を理解する必要があります.
    • 例えば
  • では、1つの10 1 5 2 3数列が与えられたときに最初の反復が行われると、1 5 2 3 10数列が得られる.つまり、1 5 2 3は10未満の数字なので、1つずつ進みます.
  • はこのような事実に基づいて,最も前進した数字が最大反復回数であるため,この問題の正解といえる.
    • fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val numbers = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        val number = br.readLine().toInt()
        numbers.add(Pair(number, i))
    }

    val sorted = numbers.sortedBy { it.first }
    var maxMoved = 0
    sorted.forEachIndexed { index, number ->
        if (maxMoved < number.second - index) {
            maxMoved = number.second - index
        }
    }
    // 정렬된 후에도 checked == false 임을 확인하기 위한 for 문을 돌기 때문에 +1을 해줍니다.
    bw.write("${maxMoved + 1}")

    br.close()
    bw.close()
}

    時間の複雑さ


    O(N * logN)
    ベクトル
    マルチスレッドテスト