-
挺喜欢这道题，可惜大号已经红了，又不想要估值，只能用小号交。
-
A 与 B 在玩游戏，其中 A 先手。
-
有 \(n\) 个数 \(a_1-a_n\)，A 每次可以任意取一个数，B 每次会取没有被取的数中下标最小的一数。保证 \(n\) 为偶数。
-
A 想最大化自己拿到的数字和。他可以选择一个数字 \(k \in [0,n)\)，把第 \(1\) 至第 \(k\) 个数依次提到数组的最后面，来实现他的目的。\(k=0\) 时，相当于不做操作。
-
求 \(k\) 与最大化数字和。
-
首先我们猜测，最大的 \(n/2\) 个数字可以被一起选走。
-
利用那个大一点的样例一试，还真可以！
-
那么，如何构造这样的 \(k\) 呢？
-
数字大小已经不重要了，按照它们是否是最大的 \(n/2\) 个数，我们把它们替换为 \(0/1\)。
-
A 不能让 B 取到 \(1\)。如果第 \(i\) 步时失败了，说明前 \(2i\) 个数中 \(1\) 的个数超过 \(0\) 的个数。
-
不妨把条件放宽点，我们尝试让前缀的任意 \(i\) 个数 \(1\) 的个数不多于 \(0\) 的个数。
-
看到不多余与前缀，就想到 Catalan，就想到折线图。
-
上折线图，\(1\) 表示往上走一步，\(0\) 表示往下走一步。则折线图不能走到 \(0\) 之上。
-
只要从折线图的最高点出发，就一定不会走到 \(0\) 之上。因为起点终点的高度都是 \(0\)，前面任意数放到最后面时高度都是原有高度，所以不会超过原折线图最高点。
-
-
上面是 \(6\) 个数的一个例子（cnblogs 图床，看不到请移步）