题解：P16212 [ECUSTPC 2025] 秋色堡垒

a_small_OIer · 2026-04-27 16:06:49 · 题解

题目大意

给定 T 个询问，每个询问给定 n,x,y，要求在 \left \lfloor \frac{n}{2} \right \rfloor 次操作内，每次从数组 a 中选出两个数 a_i,a_j，使 D 加上 a_i\times x+a_j\times y 或 a_i\times y+a_j\times x，求 D 的最大值。

思路分析

考虑贪心，显然每次要从 a_i\times x+a_j\times y 或 a_i\times y+a_j\times x 中选择较大的加到 D上。

故我们先将 a 从大到小排序，考虑比较 a_i\times x+a_j\times y 和 a_i\times y+a_j\times x 的大小（假定 x>y，令 k=\left \lfloor \frac{n}{2} \right \rfloor）。

• $$D=x \times \sum_{i=1}^{k}a_i +y \times \sum_{i=k+1}^{2k} a_i $$
• $$D=x \times \sum_{i=n-2k+1}^{n-k}a_i +y \times \sum_{i=n-k+1}^{n} a_i $$
• $$D=x \times \sum_{i=1}^{k}a_i +y \times \sum_{i=n-k+1}^{n} a_i $$

考虑到最终解可能为负，所以答案取最大值即可。

那么解法也就显而易见了，我们只需要维护一个前缀和，再根据 x,y 的大小计算答案即可。

时间复杂度

排序 O(n\log n) 和计算 O(d)，共计 O(n\log n)。