题目链接：Codeforces Gym 102538 F

有 $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;
}