F. 基里尔与蘑菇 详细题解

题目核心理解

有 $n$ 个蘑菇，第 $i$ 个蘑菇的魔力值为 $v_i$。 基里尔可以选择 $k$ 个蘑菇来炼制强度最大的药剂：

• 若选 $k$ 个蘑菇，则排列 $p$ 中前 $k-1$ 个位置对应的蘑菇魔力值会变为 $0$，不能使用。
• 药剂强度 = 所选蘑菇个数 × 这些蘑菇中的最小魔力值。
• 在所有能达到最大强度的方案中，要求使用蘑菇数量 $k$ 尽可能小。

---

核心思路

1. 关键观察

• 对每个 $k$，能使用的蘑菇是：没被清零且魔力值最大的 $k$ 个。
• 强度等价于：$k \times$ 这 $k$ 个蘑菇里魔力值最小的那一个。
• 随着 $k$ 增大，会新增一个蘑菇（$p_k$）被强制清零，我们只需要动态维护当前可用的最大蘑菇集合。

2. 贪心策略

1. 将所有蘑菇按魔力值从大到小排序。
2. 从小到大枚举 $k$（使用蘑菇数量）：
   • 每次 $k$ 增加，把 $p_{k-1}$ 位置的蘑菇标记为不可用（清零）。
   • 用一个指针 $j$ 不断向后取未清零、未被选过的最大蘑菇，直到凑齐 $k$ 个。
3. 对每个合法 $k$ 计算强度，维护最大强度和对应的最小 $k$。

---

算法流程

1. 读入 $n$、数组 $v$ 和排列 $p$。
2. 把蘑菇按（魔力值，下标）降序存入列表并排序。
3. 维护两个布尔数组：
   • $zero[i]$：下标 $i$ 的蘑菇是否被清零。
   • $used[i]$：下标 $i$ 的蘑菇是否已被选中。
4. 用指针 $j$ 从最大魔力值开始遍历，枚举 $k=1$ 到 $n$：
   • 标记 $p_{k-1}$ 为 $zero$。
   • 跳过所有不可用蘑菇，找到第 $k$ 个可用蘑菇。
   • 用当前最小魔力值计算强度。
   • 更新最大强度和最优 $k$。
5. 输出最大强度和对应的最小蘑菇数量。

---

公式与复杂度分析

对每个 $k$，强度计算公式：

$$strength = k \times \min(\text{前 }k\text{ 大的可用蘑菇魔力值}) $$

复杂度

• 排序：$O(n\log n)$
• 线性枚举 + 指针遍历：$O(n)$
• 总时间复杂度：$O(n\log n)$

可完美处理 $n\le 2\times10^5$、多组数据总和限制。