题目描述
桌面上一共有 $2n$ 个整数,分别为 $a_1,a_2,\cdots,a_{2n}$.
Alice 和 Bob 两人会轮流操作,共操作 $n-1$ 轮。每轮操作,Alice 会先删除一个整数,Bob 随后再删除一个整数。
假设最终剩下的整数为 $x,y$,那么本轮游戏的得分即 $d=x+y$.
Alice 希望最大化 $d$ 的值,而 Bob 希望最小化 $d$ 的值。
我们假设双方都是绝对聪明的,问最后 $d$ 的值是多少?
输入格式
第一行包含一个正整数 $n$ $(1\le n\le 10^5)$.
第二行包含 $2n$ 个整数 $a_1,a_2,\cdots,a_{2n}$ $(0\le a_i\le 10^9)$.
输出格式
一个整数 $d$,表示在双方都采用最优策划的前提下,这轮游戏最终的得分。
提示
Alice 先删除数字 $4$,Bob 随后删除数字 $0$,最后游戏的得分为 $2+3=5$.