商品の入出荷 2 Python3編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
同じ種類の商品について、以下のような 2n 個の入出荷情報が与えられます。
・ i 番目の出荷情報は整数の組 (a_i, b_i) で表される。
・ a_i = 1 のとき、商品が入荷されることを表す。
・ a_i = 2 のとき、商品が出荷されることを表す。
・ 入荷または出荷される商品の個数は常に 1 である。
・ b_i は、入荷の場合、入荷可能な最後の時刻を、出荷の場合、出荷可能な最初の時刻を表す。
・ 入荷情報および出荷情報はそれぞれちょうど n 個ずつ存在する。
与えられた入出荷情報をもとに、各商品の入荷と出荷をすべて組み合わせる方法であって、(出荷時間 - 入荷時間) の総和が最小になるものについて、その値を求めてください。
ここで、各商品の入荷と出荷を組み合わせる方法とは、整数 1 から 2n までの並べ替え p_1, p_2, ..., p_{2n} であって、
a_{p_2k} = 1 かつ a_{p_{2k+1}} = 2 (1 ≦ k ≦ n) を満たすもののことを指します。
例えば、入力例 1 では、時刻 1, 2 に入荷期限があり、時刻 3, 4 に出荷開始があります。
よって、それぞれの時刻の情報の番号を順に 1, 2, 3, 4 とすると、
(1, 3), (2, 4) および (1, 4), (2, 3) の 2 通りの組み合わせについて、
それぞれ (出荷時間 - 入荷時間) の総和が (3 - 1) + (4 - 2) = (4 - 1) + (3 - 2) = 4 となり、最小値は 4 となります。
(このときの入荷時間および出荷時間は入荷期限および出荷開始に一致します。)
なお、入荷時刻が出荷時刻よりも真に早いか同じ場合のみ、入荷と出荷の組み合わせが可能であるものとします。
- 入力される値
-
n
a_1 b_1
a_2 b_2
...
a_2n b_2n
・ 1 行目に、入出荷情報の個数 (の半分) を表す整数 n が与えられます。
・ 続く 2n 行に、整数 a_i, b_i が半角スペース区切りで与えられます。a_i が 1 の場合は入荷、2 の場合は出荷を表します。b_i は商品の入荷可能な最後の時刻または出荷可能な最初の時刻を表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、(出荷時間 - 入荷時間) の総和の最小値を整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 50000 = 5 × 10^4
・ 1 ≦ a_i ≦ 2 (1 ≦ i ≦ 2n)
・ a_i = 1 となる i はちょうど n 個存在する
・ a_i = 2 となる i はちょうど n 個存在する
・ 1 ≦ b_i ≦ 100000 = 10^5
・ b_i ≠ b_j (1 ≦ i, j ≦ 2n, i ≠ j) (与えられる入荷可能な最後の時刻および出荷可能な最初の時刻はすべて異なる)
- 入力例1
-
2
1 1
1 2
2 3
2 4
- 出力例1
-
4
- 入力例2
-
3
2 500
1 100
1 200
2 300
1 600
2 400
- 出力例2
-
400
