#1535. 轮流选卡

    ID: 1535 传统题 文件IO:twopick 1000ms 256MiB 尝试: 1 已通过: 1 难度: 普及 上传者: 标签>2026 高新区信息学科普日活动初中组基础算法排序贪心

轮流选卡

本题需要文件读写

文件 IO 为:输入文件 twopick.in,输出文件 twopick.out。请使用上述文件名读入和输出。

问题描述

桌上有 2N2N 张任务卡,编号为 11 到 2N2N。第 ii 张卡对甲方的计分值为 AiA_i,对乙方的计分值为 BiB_i。

甲、乙轮流从未被选择的卡中取一张,甲先手,直到所有卡都被取完。甲取到第 ii 张卡时获得 AiA_i 分,乙取到时获得 BiB_i 分。

甲最终得分总和为 XX,乙为 YY。甲希望 X−YX-Y 尽可能小,乙希望 X−YX-Y 尽可能大。双方都采用最优策略,请求出最终的 X−YX-Y。

输入格式

从文件 twopick.in 中读入数据。

第一行输入一个整数 NN。

第二行输入 2N2N 个整数 A1,A2,…,A2NA_1,A_2,\ldots,A_{2N}。

第三行输入 2N2N 个整数 B1,B2,…,B2NB_1,B_2,\ldots,B_{2N}。

输出格式

输出到文件 twopick.out 中。

输出一行一个整数,表示双方采用最优策略时 X−YX-Y 的值。

样例输入 1

1
100 200
150 300

样例输出 1

-200

样例输入 2

3
100 200 350 400 550 600
400 200 300 100 150 500

样例输出 2

-50

评测数据规模

  • 1≤N≤10001\le N\le1000;
  • 1≤Ai,Bi≤1091\le A_i,B_i\le10^9;
  • 输入均为整数。