分数: 400 点
问题陈述
有 N 高桥和青木面前摆着的菜肴。 为了方便起见,我们将这些菜肴称为Dish 1,菜 2, ..., 菜 N.
当高桥吃菜时 i,他赚了 A_i 点 幸福;当青木吃菜的时候 i,她赚了 B_i 点幸福。
从高桥开始,轮流选一道菜吃,直到没有菜可吃了。 这里,两人选择菜肴时使得以下值最大化:“他/她最终获得的幸福感之和”减去“对方最终获得的幸福感之和”。
求值:“高桥最终获得的幸福感之和”减去“青木最终获得的幸福感之和”。
约束
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 : A_N B_N
输出
打印值:“高桥最终获得的幸福感之和”减去“青木最终获得的幸福感之和”。
示例输入 1
3 10 10 20 20 30 30
示例输出 1
20
在此示例中,他们两人都获得了 10 通过吃菜获得幸福点 1, 20 吃菜积分 2,和 30 吃菜积分 3.
在这种情况下,由于高桥和青木有相同的“口味”,所以每次他们都会选择能给自己带来最大幸福的菜肴。因此,高桥首先会选择Dish 3,那么Aoki会选择Dish 2,最后高桥会选择Dish 1,所以答案是 (30 + 10) - 20 = 20.
示例输入 2
3 20 10 20 20 20 30
示例输出 2
20
在此示例中,高桥赚取 20 吃任意一道菜即可获得幸福点 1, 2 和 3,但青木赚了 10 通过吃菜获得幸福点 1, 20 吃菜积分 2,和 30 吃菜积分 3.
在这种情况下,由于只有青木有好恶,所以每次他们都会选择青木能获得最大幸福的菜肴。因此,高桥首先会选择Dish 3,那么Aoki会选择Dish 2,最后高桥会选择Dish 1,所以答案是 (20 + 20) - 20 = 20.
示例输入 3
6 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
示例输出 3
-2999999997
请注意,答案可能不适合 您将获得一个由 32位整数。