#P13688. [ARC121D] 1 or 2

    ID: 12890 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高暴力枚举排序贪心交换论证

[ARC121D] 1 or 2

题目描述

你有 nn 个糖果,第 ii 个糖果的美味值为 aia_i。

你需要吃糖,每次你可以选择吃 11 个或 22 个糖,并将你这一次吃的糖的总和写在黑板上。

你需要求出吃完所有糖果的所有可能的情况中,黑板上数字最大值和最小值之差最小是多少。

输入格式

如原文。

输出格式

如原文。

输入输出样例 #1

输入 #1

3
1 2 4

输出 #1

1

输入输出样例 #2

输入 #2

2
-100 -50

输出 #2

0

输入输出样例 #3

输入 #3

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

输出 #3

13

说明/提示

1≤n≤5×103,−109≤ai≤1091\leq n\leq 5\times 10^3,-10^9\leq a_i\leq 10^9。


样例一:

第一次吃第一和第二个,第二次吃第三个,黑板上的数为 {3,4}\{3,4\},答案为 11。

样例二:

第一次全部吃完,黑板上的数为 {−150}\{-150\},答案为 00。

Translate by Zek3L.