#AGC025C. [AGC025C] Interval Game
[AGC025C] Interval Game
题目描述
高橋君と青木君は数直線と区間を使ってゲームをすることにしました。 高橋君は数直線上に立っており、最初は座標 にいます。 また、青木君は 個の区間を持っており、 個目の区間は 、つまり座標が 以上 以下の点からなる区間となっています。
このゲームは 回のステップからなります。 ステップ目では以下の手順を踏みます。
- まず青木君は、 個の区間の内、まだ選んでいない区間を一つ選び、その区間を高橋君に伝える。
- 次に高橋君は、青木君が今回選んだ区間に入るように、数直線上を移動する。
回のステップを終えた後、高橋君が座標 まで戻ることでゲームは終了します。
高橋君がゲーム全体を通して移動する距離の合計を としたとき、青木君は ができるだけ大きくなるように区間を選び、 高橋君は ができるだけ小さくなるように移動します。 このとき、最終的に高橋君の移動距離の合計 はいくつになるでしょうか。
输入格式
入力は以下の形式で標準入力から与えられる。
:
输出格式
高橋君と青木君が上記の条件に従って行動するときの高橋君が動く距離の合計を、 つの整数値として出力せよ。 ただし、 が整数であるとき、 が整数となることは保証されている。
题目大意
- 数轴上有 个闭区间,第 个闭区间为 .
- A 和 B 玩游戏,A 初始在原点 ,每次 B 选择一个还未选过的区间,A 要走到任意一个属于该区间的点。最后 A 要回到 .
- A 希望最小化自己走过的路程,B 希望最大化 A 走过的路程,在两者都采取最优策略的情况下,求 A 走过的路程。
- ,.
3
-5 1
3 7
-4 -2
10
3
1 2
3 4
5 6
12
5
-2 0
-2 0
7 8
9 10
-2 -1
34
提示
制約
- と は整数
Sample Explanation 1
高橋君と青木君の行動の一例は以下のようになります。 - 青木君が 番目の区間を選び、高橋君は座標 から座標 まで距離 だけ移動する。 - 青木君が 番目の区間を選び、高橋君は座標 のまま動かない - 青木君が 番目の区間を選び、高橋君は座標 から座標 まで距離 だけ移動する。 - 高橋君は座標 から座標 まで距離 だけ移動する。 このとき高橋君の移動距離の合計は になってしまうので、高橋君の行動は最適ではないですが、 動き方を変えることで、移動距離の合計を にすることができます。