There are $n$ bricks numbered from $1$ to $n$. Brick $i$ has a weight of $a_i$.
Pak Chanek has $3$ bags numbered from $1$ to $3$ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.
After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $w_j$ be the weight of the brick Bu Dengklek takes from bag $j$. The score is calculated as $|w_1 - w_2| + |w_2 - w_3|$, where $|x|$ denotes the absolute value of $x$.
It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?
/*
***在决策者以最小分值玩游戏的限制下,问我们如何设置游戏资源,使得分最大***
首先,对a进行排序。现在我们将一直使用排序后的数组a.
pj作为从袋子j取出来的砖块索引,p1,p2,p3有以下4种情况:
1.p1 < p2 < p3
2.p1 > p2 > p3
3.p2 < min(p1, p3)
4.p2 > max(p1, p3)
现在请注意第三种,让我们考虑min(p1, p3) > p2 + 1的情况。如果是这种情况,让我们来看下索引p2 + 1的
所有放置可能。
1.袋子1,因a(p2 + 1) - a(p2) <= a(p1) - a(p2),故决策者会选择p2 + 1作为袋子1的p1
2.袋子2,因为a(p2) <= a(p2 + 1),决策者会选择P2 + 1
3.袋子3与袋子1同理
故欲使分值最大,p2 + 1 = min(p1, p3) 更合理
类似的逻辑也可以用于第四种情况,max(p1,p3) = p2 - 1
为了使得分最大化,对于p1,p2,p3而言,第三,四种情况更为理想化。
对于第三种情况,最大化max(p1,p3)更理想,我们使max(p1,p3) = n;
对于第四种情况,最小化min(p1,p3)更理想,我们使min(p1,p3) = 1.
因此,获得最大得分的情况有二种:
ai - a(i - 1) + a(i) - a1, 3 <= i <= n;
a(i + 1) - ai + a(n) - ai, 1 <= i <= n - 2
*/