1. 题意理解

H 个英雄和 M 只怪兽排成一个圈，顺序是：

H₁ (m₁只怪兽) H₂ (m₂只怪兽) ... H_H (m_H只怪兽)

战斗规则：

• 从第 1 位英雄开始轮流行动
• 每位英雄可以攻击任意一只怪兽（造成 1 点伤害）
• 每只怪兽需要 K 次攻击才会死亡
• 怪兽可以攻击任意英雄（无论位置）
• 目标：最小化英雄受到的总攻击次数

---

2. 关键观察

由于怪兽可以任意选择攻击目标，最优策略是尽快减少怪兽的数量，因为每只存活的怪兽在每个英雄回合后都会攻击一次。

问题转化为：如何安排英雄的攻击顺序，使得怪兽的总存活时间最短。

---

3. 代码解法分析

3.1 数据结构

int fa[N];  // 并查集，用于快速找到下一个有怪兽的位置

fa[i] 表示从位置 i 开始，下一个有怪兽的位置（循环）。

---

3.2 初始化

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    fa[i] = ((a[i] == 0) + i - 1) % n + 1;  // 如果a[i]=0，指向下一个位置
    m += a[i];
}

---

3.3 周期分析

int t = n / gcd(n, k);  // 攻击模式的周期
long long base = t * k / n;  // 每个周期的基础攻击次数

由于英雄按顺序循环攻击，攻击位置模式每 t 个英雄行动后重复。

---

3.4 主循环

阶段 1：批量处理

// 计算每个位置在每个周期中被攻击的次数 num[i]
for (int i = 1; i <= t; i++) {
    p[i] = (k * i - 1) % n + 1;  // 第i次攻击的位置
    val[i] = (k * i - 1) / n + (find(p[i]) < p[i]);  // 计算额外的攻击轮次
    num[find(p[i])]++;  // 统计每个位置被攻击次数
}

找到最小的完整周期数 minn，可以批量处理：

for (int i = 1; i <= n; i++)
    if (num[i])
        minn = min(minn, a[i] / num[i]);

批量减少怪兽数量：

m -= t * minn;
for (int i = 1; i <= n; i++) {
    a[i] -= num[i] * minn;
    if (!a[i]) fa[i] = i % n + 1;  // 更新并查集
}

更新答案：

for (int i = 1; i <= t; i++)
    ans += val[i] * minn + minn * (2 * cnt + minn - 1) / 2 * base;
cnt += minn;

阶段 2：逐个处理

当不能再批量处理时，逐个英雄进行攻击：

for (int i = 1; i <= t; i++) {
    int p = (k * i - 1) % n + 1;
    int val = (k * i - 1) / n + (find(p) < p);
    p = find(p);  // 找到实际攻击的位置
    a[p]--;
    if (!a[p]) fa[p] = p % n + 1;
    m--;
    ans += val + base * cnt;
    if (!m) break;
}
cnt++;

---

4. 算法思想

4.1 核心思路

• 利用攻击模式的周期性，批量处理多个完整周期
• 使用并查集快速找到下一个可攻击的怪兽位置
• 通过数学公式直接计算批量处理的攻击次数，避免模拟每个回合

4.2 答案计算

总攻击次数 = 英雄行动次数 × 存活的怪兽数量

• 在批量处理阶段，用等差数列求和公式计算
• 在逐个处理阶段，直接累加

---

5. 样例验证

样例 1: n=3, k=1, a=[0,3,3]

• 输出 3，符合样例

样例 2: n=3, k=2, a=[0,3,3]

• 输出 10，符合样例

---

6. 复杂度分析

• 并查集操作：O(α(n))，近似 O(1)
• 主循环：最多 O(M/t) 次批量处理 + O(t) 次逐个处理
• 总复杂度：O(H + M/t × H)，对于 M ≤ 1e9 可接受

---

7. 算法标签

• 周期分析 (Periodicity Analysis)
• 并查集优化 (Union-Find Optimization)
• 批量处理 (Bulk Processing)
• 数学公式计算 (Mathematical Formula)

---

8. 核心思想总结

1. 识别周期性：英雄攻击位置模式具有周期性，利用 gcd 计算周期长度
2. 批量处理：在周期模式稳定时，批量减少怪兽数量
3. 快速定位：用并查集跳过没有怪兽的位置，提高效率
4. 数学优化：通过公式直接计算攻击次数，避免逐轮模拟

这种方法高效处理了大规模数据，避免了 O(M) 的模拟复杂度。