← 返回题目列表

AtCoder · nikkei2019_qual_c

C. 不同的笔画

中文机器翻译题面 查看原题

分数: 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位整数。