题目详解

问题重述

我们有一个 $n \times m$ 的网格，需要放置 $w$ 只大猩猩（每只大猩猩有身高 $a_i$，每个格子最多放一只）。定义观赏值为：所有边长为 $k$ 的子正方形的观赏值之和，其中每个子正方形的观赏值等于其中所有大猩猩身高之和。

我们需要最大化这个总观赏值。

---

核心思路

1. 每个格子对总观赏值的贡献次数

关键观察：
对于网格中的某个格子 $(i, j)$（这里 $i, j$ 从 $0$ 开始索引），它会被多少个边长为 $k$ 的子正方形覆盖？

推导方法

一个边长为 $k$ 的子正方形由其左上角 $(x, y)$ 唯一确定，其中：

• $0 \le x \le n - k$
• $0 \le y \le m - k$

格子 $(i, j)$ 被该子正方形覆盖，当且仅当：

• $x \le i \le x + k - 1$ $\quad\Rightarrow\quad$ $i - k + 1 \le x \le i$
• $y \le j \le y + k - 1$ $\quad\Rightarrow\quad$ $j - k + 1 \le y \le j$

同时 $x$ 必须满足 $0 \le x \le n - k$，$y$ 必须满足 $0 \le y \le m - k$。

因此 $x$ 的取值范围是：

$$x_{\min} = \max(0, i - k + 1), \quad x_{\max} = \min(i, n - k) $$

$y$ 的取值范围是：

$$y_{\min} = \max(0, j - k + 1), \quad y_{\max} = \min(j, m - k) $$

所以格子 $(i, j)$ 被覆盖的次数为：

$$cnt(i, j) = (\min(i, n - k) - \max(-1, i - k)) \times (\min(j, m - k) - \max(-1, j - k)) $$

注意：代码中使用 max(-1LL, i - k) 是因为当 $i - k = -1$ 时，$\max(-1, -1) = -1$，相减后得到 $i - (-1) = i + 1$，等价于 $i - (i - k + 1) + 1 = k$。实际上更清晰的写法是：

$$cnt(i, j) = (\min(i, n - k) - \max(0, i - k + 1) + 1) \times (\min(j, m - k) - \max(0, j - k + 1) + 1) $$

但原代码的写法在数学上是等价的。

---

2. 贪心策略

总观赏值可以写成：

$$\text{总观赏值} = \sum_{\text{每个子正方形}} \sum_{\text{格子在子正方形中}} a_{格子} = \sum_{\text{每个格子}} cnt(i, j) \times a_{格子} $$

也就是说，每个格子的“重要性”就是它被覆盖的次数 $cnt(i, j)$。

为了最大化总和，我们应该：

• 将最大的 $cnt(i, j)$ 分配给最大的 $a$（身高）
• 将第二大的 $cnt(i, j)$ 分配给第二大的 $a$
• 以此类推

这就是一个典型的贪心策略：大的乘大的，小的乘小的。

---

3. 算法步骤

1. 计算每个格子的覆盖次数 $cnt(i, j)$，存入数组 prr。
2. 对大猩猩身高数组 arr 从大到小排序。
3. 对覆盖次数数组 prr 从大到小排序。
4. 计算 $\sum_{i=0}^{w-1} prr[i] \times arr[i]$（注意只有前 $w$ 个格子被放置大猩猩，因为 $w \le n \times m$，未被使用的格子贡献为 $0$）。

---

时间复杂度分析

• 计算所有 $n \times m$ 个格子的覆盖次数：$O(n \cdot m)$
• 排序 arr：$O(w \log w)$
• 排序 prr：$O(n \cdot m \log(n \cdot m))$
• 总复杂度：$O(n \cdot m \log(n \cdot m) + w \log w)$

由于所有测试用例的 $n \cdot m$ 之和不超过 $2 \times 10^5$，$w$ 之和也不超过 $2 \times 10^5$，因此可以在时限内运行。

---

代码对应关系

函数/变量	作用
calcc(i, j)	计算格子 $(i, j)$ 被覆盖的次数 $cnt(i, j)$
build()	1. 将 arr 降序排序 2. 遍历所有格子，计算覆盖次数存入 prr 3. 将 prr 降序排序
solve()	计算 $\sum_{i=0}^{w-1} prr[i] \times arr[i]$

---

示例验证（第一个测试用例）

$n = 3, m = 4, k = 2, w = 9$
所有 $a_i = 1$，所以任何安排结果相同。

先计算覆盖次数矩阵（$3 \times 4$）：

手动计算几个：

• 角上格子 $(0,0)$：能被左上角在 $(0,0)$ 的 $2\times 2$ 子正方形覆盖，只有 $1$ 个 → $cnt = 1$
• 边中格子 $(0,1)$：能被左上角在 $(0,0)$ 和 $(0,1)$ 的两个子正方形覆盖 → $cnt = 2$
• 中心格子 $(1,1)$：能被左上角在 $(0,0),(0,1),(1,0),(1,1)$ 的 $4$ 个子正方形覆盖 → $cnt = 4$

覆盖次数矩阵：

1 2 2 1
2 4 4 2
1 2 2 1

总观赏值 = $1+2+2+1+2+4+4+2+1+2+2+1$? 不对，需要乘以身高（都是 $1$）。

实际上，总观赏值 = 所有覆盖次数之和 = $1+2+2+1+2+4+4+2+1+2+2+1 = 24$？但答案是 $21$。

这里需要小心：我们只有 $w = 9$ 只大猩猩，不是 $12$ 个格子。
所以我们要取覆盖次数最大的 $9$ 个格子：$4,4,2,2,2,2,2,2,1$？
排序后：$4,4,2,2,2,2,2,2,1$
和 = $4+4+2+2+2+2+2+2+1 = 21$ ✅

---

注意事项

1. 使用 long long 存储结果，因为身高最大 $10^9$，覆盖次数最大约 $k^2$（但 $k \le \min(n,m)$），乘积可能很大。
2. 覆盖次数计算时，注意边界条件，尤其是 $n = k$ 或 $m = k$ 的情况。
3. 如果 $w < n \cdot m$，只使用覆盖次数最大的 $w$ 个格子，其余格子不放大猩猩。