BOJ #15922

4596 ワード
greedy アルゴリズム#アルゴリズム# テキストリンク

LEVEL :
Gold5
質問の概要:
所与の線分を求めるときに線分を形成する長さ.線分を重ねることができます.
ソリューション:
正直金色5問じゃないみたいこれはあまりにも簡単なメカニズムです.
x座標が所定に整列していない場合は、より困難になる可能性があります.
現在の線分から、次の所与の線分が現在の線分と重なるかどうかを計算します.重複している場合は、現在のセグメントがより長いセグメントに延長されているかどうかを確認し、現在のセグメントを変更します.オーバーラップしない場合は、進行中の現在のセグメント長をsumに追加し、新しいセグメントを現在のセグメントに接続します.
コードを見ると上の説明が分かりやすいはずです.
時間の複雑さ:
時間的複雑さはO(N)で解決できる問題である.
Solution
import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n = int(input().strip())
    lines = [list(map(int,input().strip().split())) for _ in range(n)]
    length = 0
    cur = lines[0]
    for line in lines :
        if cur[1] > line[0] :
            cur[1] = max(cur[1],line[1])
        else :
            length += cur[1] - cur[0]
            cur = line
    length += cur[1] - cur[0]
    print(length)
共通データ21の使用(フィードバック反映)
mファイルだけがこの間違いを報告します