コドフォ Educational Contest 92 D Segment Intersections 解説[python]

概要

　区間[l1,r1],[l2,r2] のがそれぞれN 本ある。
i 番目の[l1,r1]区間はi 番目の[l2,r2]区間と対応する。

任意の区間の距離を長さ１伸ばすのにstepが1かかる。（左右両方向に伸ばせる）

　それぞれの対応する区間同士が重なっている長さの合計をk以上にするのにかかる最低のstep数を答えよ。

制約

n <= 2*10**5

1<= l,r,k <=10**9

考察

　
　性質として、現在重なっていて、対応する区間同士にまだ重なっていない部分があるなら、そこを使い切るまでコスト1で長さを1伸ばせる。

　使い切っているならば、現在重なっていない区間をgapを埋めて使い切るか(選択1)

、現在重なっている区間に関して、両方の端を伸ばして、コスト2で長さを1伸ばすか(選択2)
の２つの選択肢がある。

　選択2の時、gap分だけコストがかかるので、解を決めうつと条件分岐が少なく実装が楽になる。

　場合わけとして

• 元から対応する区間の重なりの合計がkを超えている => 答え 0
• 元から対応する区間は重なっており、全てを重ねた時の区間の長さの合計がk 以下 => k
• 元から対応する区間は重なっており、全てを重ねた時の区間の長さの合計がk 以上 => 全ての区間に対して、重なっていない部分を使い切るまで伸ばして、そのあとはコスト2で伸ばす
• 初期値では区間は重なっていない => 何本の区間を重なるようにするか決めうつ

実装

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    n, k = map(int, input().split())
    l1, r1 = map(int, input().split())
    l2, r2 = map(int, input().split())
    origin_inter = max(0, min(r1, r2) - max(l1, l2))
    ans = 0
    k -= origin_inter * n
    if k <= 0:
        ans = 0
    elif origin_inter > 0:
        # まず伸ばせるまで伸ばす。その後、2ターンで1伸ばす
        if k <= n * ((r1 - l1) + (r2 - l2) - origin_inter * 2):
            ans += k
        else:
            ans = 2 * k - n * ((r1 - l1) + (r2 - l2) - origin_inter * 2)
    else:
        margin = max(l1, l2) - min(r1, r2)
        len_inter = max(r1, r2) - min(l1, l2)
        # 何本を使うかを決め打つ
        ans = 10 ** 10
        for i in range(1, n + 1):
            tmp_i = margin * i
            if k > len_inter * i:
                tmp_i += len_inter * i + (k - len_inter * i) * 2
            else:
                tmp_i += k
            # print(i, tmp_i, margin, len_inter)
            ans = min(tmp_i, ans)
    print(ans)