AT_iroha2019_day3_f 闇のカードゲーム
题目描述
桌上整齐地摆放着NNN张卡片（NNN为奇数），每张卡片上有一个正整数。卡片按整数从小到大排列，位于第iii张卡片上的整数为aia_iai。不同的卡片上不会有相同的整数。
すぬけ君和いろはちゃん轮流进行操作，直到桌面上仅剩下 2 张卡片。すぬけ君作为先手，双方依次进行以下操作：
操作：从当前桌面上选择一张卡片将其拿走并移除。
游戏结束时，剩下两张卡片上的整数差的绝对值即为游戏的得分。
在进行游戏时，先手和后手需遵循以下规则：
- すぬけ君（先手）必须选择当前桌面上居中的那张卡片。假设当前剩余卡片数为rrr，他必须拿走第(r+1)/2(r+1)/2(r+1)/2张卡片。
- いろはちゃん（后手）必须从剩余卡片中选择最左或最右的一张。
假设いろはちゃん始终以最优策略行事以使得游戏得分最小化，求出最终的游戏得分。
输入格式
输入通过标准输入给出，格式如下：
$ N $ $ a_1\ a_2\ \cdots\ a_N $
输出格式
输出游戏结束时的得分，即两张剩余卡片上整数差的绝对值。
输入输出样例 #1
输入 #1
3 1 5 100输出 #1
99输入输出样例 #2
输入 #2
9 3 14 15 20 33 51 59 62 68输出 #2
45说明/提示
- NNN是奇数，3≤N≤1053 \leq N \leq 10^53≤N≤105。
- 卡片上的整数aia_iai满足1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109。
- 所有aia_iai均为整数且互不相同。
示例解释
すぬけ君在第一回合可能会选择从左数的第 2 张卡片，然后游戏结束。
本翻译由 AI 自动生成
对手会删去⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n⌋个数，那么最后剩下的两数在最开始一定相距⌊n2⌋+1\left\lfloor\dfrac{n}{2}\right\rfloor+1⌊2n⌋+1个位置。我们要通过lll和rrr来调节对手删去的数，公式就为mini=1⌊n2⌋∣ai−ai+⌊n2⌋+1∣\min\limits_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}|a_i-a_{i+\left\lfloor\frac{n}{2}\right\rfloor+1}|i=1min⌊2n⌋∣ai−ai+⌊2n⌋+1∣。
