「Codeforces Gym 102538F」Farm of Monsters

题目链接:Codeforces Gym 102538F

有 $n$ 个怪物,第 $i$ 个怪物有 $h_{i}$ 的血量。

你和对手要合力击杀这些怪物,你的攻击力为 $a$,对手的攻击力为 $b$。你们要轮流对活着的怪物进行攻击,你是先手。每次攻击,怪物都会损失攻击者的攻击力的血量。如果某一回合后被攻击怪物的血量非正,则它将会死亡,击杀它的人会得到 $1$ 分。当所有怪物都死亡后,游戏结束。

在你的回合,你可以选择任意攻击一只活着的怪物,也可以选择不进行攻击。

在对手的回合,对手会选择当前活着的、编号最小的怪物进行攻击。

如果你合理安排攻击策略,请求出你能获得的最大得分。

数据范围:$1 \le n \le 3 \times 10 ^ {5}$,$1 \le a, b, h_{i} \le 10 ^ {9}$。


Solution

设最终在第 $i$ 只怪物上的得分为 $x_{i} \in \{0, 1\}$,可以发现:

  • 假如 $x_{i} = 0$,那么我们一定不会对第 $i$ 只怪物进行任何攻击。
  • 假如 $x_{1} = 1$,那么我们的攻击策略一定是:先进行次数尽量少的攻击,然后在对手攻击若干次后,最后将其一击毙命。

对于第 $i$ 只怪物,你和对手的攻击次数分别为 $p_{i}, q_{i}$。对两种情况的攻击次数分别计算:

  • $x_{i} = 0$:完全让对手杀死这只怪物。

$$ \begin{align} p_{i, 0} & = 0 \\ q_{i, 0} &= \left\lfloor{\frac{h_{i} - 1}{b}}\right\rfloor + 1 \end{align} $$

  • $x_{i} = 1$:进行 $r$ 次的攻击后,满足 $(h_{i} - r \cdot a) \bmod b \in [1, a]$,即 $((h_{i} - 1) - r \cdot a) \in [0, a)$,从中可以解得最小的 $r$。

$$ \begin{align} p_{i, 1} & = r + 1 = \left\lfloor\frac{(h_{i} - 1) \bmod b}{a}\right\rfloor + 1 \\ q_{i, 1} & = \left\lfloor\frac{(h_{i} - 1) - r \cdot a}{b}\right\rfloor \end{align} $$

注意到我们可以跳过若干回合,且不必按顺序攻击,这意味着我们花费在前 $i$ 只怪物上的攻击次数至多比对手多 $1$ 次。记 $d_{i, k} = q_{i, k} - p_{i, k}$,则上述限制为:

$$ \forall i, 1 + \sum_{k = 1} ^ {i} ([x_{k} = 0]d_{k, 0} + [x_{k} = 1]d_{k, 1}) \ge 0 $$

问题转化为:对于每个 $i$ 选择一个 $x_{i} = 0 / 1$ 且使对应的前缀和不小于 $0$。由于每种选择方案的 $d_{i}$ 都是已知的,可以贪心解决。具体地,假如选择 $x_{i} = 1$ 后仍然满足条件,那么直接使答案加 $1$;否则贪心地将之前(包括当前的 $i$)选择 $x_{j} = 1$ 且 $d_{j, 0} - d_{j, 1}$ 最大的 $j$ 改为 $x_{j} = 0$(由于 $d_{i, 0}$ 必然大于 $0$,所以调整之后一定可以满足限制)。整个过程可以使用优先队列维护。

时间复杂度:$\mathcal O(n \log n)$。


Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 3e5;
int n, x, y, a[N + 5], yes[N + 5], no[N + 5];

int main() {
    scanf("%d%d%d", &n, &x, &y);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        a[i]--;
        int p = (a[i] % y) / x, q = (a[i] - p * x) / y;
        p++;
        yes[i] = q - p;
        no[i] = a[i] / y + 1;
    }
    int64 sum = 1;
    int ans = 0;
    std::priority_queue<int> pq;
    for (int i = 1; i <= n; i++) {
        pq.push(no[i] - yes[i]);
        sum += yes[i];
        if (sum >= 0) {
            ans++;
        } else {
            sum += pq.top();
            pq.pop();
        }
    }
    printf("%d\n", ans);
    return 0;
}

发表评论