题目名称 3719. 有n种物品
输入输出 nit.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravatar湖岸与夜与咸鱼 于2022-07-15加入
开放分组 全部用户
提交状态
分类标签
贪心 思维 清北学堂
分享题解
通过:5, 提交:52, 通过率:9.62%
Gravatarムラサメ 100 0.058 s 2.51 MiB C++
GravatarAeeE5x 100 0.061 s 2.60 MiB C++
GravatarZRQ 100 0.129 s 2.45 MiB C++
Gravatar湖岸与夜与咸鱼 100 0.131 s 3.06 MiB C++
Gravatarsyzhaoss 100 0.214 s 2.60 MiB C++
Gravatarムラサメ 60 0.062 s 2.51 MiB C++
Gravatarムラサメ 40 0.073 s 2.51 MiB C++
GravatarAeeE5x 30 0.240 s 5.35 MiB C++
Gravatarppr 30 0.274 s 2.90 MiB C++
Gravatarppr 30 0.301 s 2.90 MiB C++
关于 有n种物品 的近10条评论(全部评论)

3719. 有n种物品

★   输入文件:nit.in   输出文件:nit.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

有$n$种物品,每种物品有两个,第$i$种物品先选的人获得的价值为$a_i$,后选获得的价值为$b_i$。小A小B轮流取物品,小A先取,每种物品每个人只能取一次。两个人都想自己取得物品的价值最大。求小A获得的价值减去小B获得的价值是多少。

【输入格式】

第一行一个整数$n$。

接下来$n$行每行两个整数$a_i,b_i$。

【输出格式】

一行一个整数表示答案。

【样例输入1】

2
2 1
1 2

【样例输出1】

0

【样例输入2】

2
2 1
2 1

【样例输出2】

0

【样例输入3】

2
1 2
1 2

【样例输出3】

-2

【样例说明】

对于第二个样例,小A先选第一件物品,小B先选第二件物品。然后两人分别选择剩下的物品。

【数据规模与约定】

对于$30\%$的数据,$n \leq 5$。

对于$50\%$的数据,$n \leq 10$。

对于另外$20\%$的数据,$a_i \geq b_i$。

对于$100\%$的数据,$n \leq 100000,1 \leq a_i,b_i \leq 10^9$

【来源】

清北学堂2022 7.15模拟T1