APCS Mar 2016 - b966 Q3 [Python]

問題文:

一次元の座標軸上にある複数の線分について、線分が覆う長さの合計を求めます。重なる部分は一度だけ数えます。例えば、(5, 6)、(1, 2)、(4, 8)、(7, 9) の4本の線分が覆う長さは、下図のように6です。

def main():
    # 讀取線段數量
    n = int(input())

    segments = []

    # 讀取每個線段的起點和終點
    for _ in range(n):
        L, R = map(int, input().split())
        segments.append((L, R))

    # 將線段按照起點進行排序
    segments.sort(key=lambda x: x[0])

    # 合併線段
    covered_length = 0
    current_start, current_end = -1, -1

    for start, end in segments:
        if start > current_end:

            # 如果當前線段與前一線段不重疊，加上前一線段的長度(因為上一步不知道下一個是否比自己大)
            covered_length += current_end - current_start
            current_start, current_end = start, end
        else:
            # 如果重疊，延伸線段的結束點
            current_end = max(current_end, end)

    # 加上最後一個線段的長度
    covered_length += current_end - current_start

    # 輸出結果
    print(covered_length)


if __name__ == "__main__":
    main()
    

この問題で使う知識

• map の書式：map(func, obj)

  例：

  map(int,input(),split())
  

• sort の書式：[(配列)].sort(key=func)

  例：

  the_list = [(0,6),(3,8),(5,7),(2,5),(1,10),(8,12),(7,10)]
  the_list.sort(key= lamba x:x[0])
  

この記事は繁体字中国語の原文をAIで翻訳したものです。意味や表現に違いがある可能性があります。正確な内容は繁体字中国語の原文をご確認ください。