题解：AT_arc186_c [ARC186C] Ball and Box

· · 题解

AT_arc186_c [ARC186C] Ball and Box

solution

设选盒子的人为 A，选球的人为 B。显然，A 在还有位置装一个球的时候一定不会买新的盒子，所以游戏停下的位置一定一开始或者某一种颜色的球的箱子装满时。A 的最优策略看起来比较难考虑，但B的就很简单了：如果 A 还没有一种颜色的球，直接选那种颜色的球；否则选盒子容量最小的那种颜色的球。

那么 A 最后选出来的盒子里面，容量前 m-1 大的盒子一定都只有一种颜色的球，后面的盒子一定会装满。否则，在它们即将装不只一个球的时候，B 可以把那个球的颜色改为目前还没有选过的那种颜色的球。

我们将盒子按容量降序排序。设 A 最终选的容量第 m-1 大的箱子在 k。那么 [1,k] 的箱子里就只有一个球，(k,n] 的箱子里都会放满 v_i 个球。

枚举第 m 大的箱子的位置，(k,n] 的箱子的最大贡献用后缀最大值是容易维护的。[1,k] 的 m-1 个箱子每个都只有 1 的贡献，所以只要选 p_i 前 m-1 小的箱子即可。维护的方法应该不少，我用的是权值线段树。

code

注意一下 m < n 和 m \le 1 的情况。

Submission。