[BOJ 1838]泡揃え(Python)

7303 ワード
ツールバーの 白駿 テキストリンク

質問する


https://www.acmicpc.net/problem/1838

並べ替え完了時に変数iに格納された値を求める問題

問題を解く


[エラーコード:道現のコードに従って使用]
for (i=0; i<N; i++) {
    flag = 0;
    for (j=0; j<N-1; j++) {
        if (A[j] > A[j+1]) {
            flag = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
    if (flag == 0) {
        break;
    }
}
これは道現がタイに勝つために書いたコードです.
バブルソートを使用して、要素を前から順に整理します.
ソートが不要になった場合にiを出力します.
このコードはPythonコードで作成され、提出されました.
[結果]
タイムアウトしました.もちろんです.
問題で与えられた要素の個数は500,000であり、上記のコードはO(n^2)である.
では、演算量は250,000,000,000個で、与えられた2秒以内に計算が完了しない.
[正しい]
問題のiが何を意味するかを考えると、簡単に解けます.
i並べ替えは不要なので、停止すると何回並べ替えたかを示す.
Bubbleソートでは、ソートのたびに最大値が最後に移動します.
これにより、[後方に移動した値](Move After Value)で[最大移動距離](Move After Max Distance)を見つけることができます.
つまり、「ソート前索引-ソート後索引>0」の値で最大値を見つけることができます.

コード#コード#

import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().rsplit()))

before = defaultdict(int)
for i,num in enumerate(a):
    before[num]=i

a.sort()

after = defaultdict(int)
for i,num in enumerate(a):
    after[num] = i

answer = 0
for num in before:
    minus = before[num] - after[num]
    if (minus > 0 and minus > answer):
        answer = minus

print(answer)
Elasticsearch単機取付
チャートの使い方.アングル13 +プロジェクト