問題概要

問題URL

$N$体の魔物はそれぞれ$h_i \; (i = 1, 2, \ldots, N)$の体力があり，体力が0以下になると消滅する．
1回の爆発毎に1体は$A$，その他の魔物は$B$減らすことができる（ただし$A > B$）．
全ての魔物を消滅させるのに必要な最小の爆発回数を求めよ．

制約

  • 入力値は全て整数
  • $1 \leq N \leq 10^5$
  • $a \leq B < A \leq 10^9$
  • $1 \leq h_i \leq 10^9$

考えたこと

$A > B$なので，1回の攻撃毎に体力が最大の魔物の体力を$A$減らすように選択すれば貪欲法によって解ける，と考えた． しかし，複数回攻撃した時点で体力が最大の魔物を見つけるには$O(N)$必要なので，攻撃回数を$T$とすると$O(NT)$の計算量である．例えば$N = 2, A = 3, B = 1, h_1 = 10^9, h_2 = 10^9$の場合は$T = 5 \times 10^8$となり，$O(NT)$では間に合わない．この方法では駄目ということは分かったが，そこから先の考察は進まなかった．

解法

解説AC．

問題の解である最小の爆発回数を$T_{min}$とする． 任意の$T \in \mathbb{N}$に対して$T_{min} \leq T$ならば，全ての魔物を消滅させることが可能である． そこで，全ての魔物を消滅させることが可能であるか否かを返す関数$enough(T)$を考えると，

\begin{align} enough(T) = \left\{ \begin{array}{l} false \quad & (T < T_{min}) \newline true \quad & (T_{min} \leq T) \end{array} \right. \end{align}

になっている．図示すると以下の通り．

fig1

以上より，$enough(T)$は単調性を持つので，二分探索によって$T_{min}$を見つけることができる．
$T$の上限は$h_i \; (i = 1, 2, \ldots, N)$の中での最大値$h_{max} := \max_{i} h_i$を$B$の 爆発だけで0以下にする場合に対応するので，$T \in [0, \mathrm{ceil}(h_{max} / B)]$と考えてよい． 制約の$1 \leq B$と$1 \leq h_i \leq 10^9$から，任意の入力に対して$T \in [0, 10^9]$で探索すればよい．

コード

#define SUBMIT

#include <bits/stdc++.h>
using namespace std;
using ui64 = uint64_t;
using i64 = int64_t;

const int MAX_N = 100000;
i64 h[MAX_N];
i64 N, A, B;
i64 diff;

int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    stringstream stream(R"(4 5 3
8
7
4
2
)");
#endif
    stream >> N >> A >> B;
    for (int i = 0; i < N; ++i) stream >> h[i];
    diff = A - B;

    i64 left = 0, right = static_cast<i64>(1e9);
    while (1 < right - left) {
        auto mid = (right + left) / 2;

        // Aで攻撃する必要がある回数の総和
        i64 sum_a_attack = 0;
        for (auto hi : h) {
            auto extra_cost = hi - mid * B;
            if (0 < extra_cost) sum_a_attack += (diff + extra_cost - 1) / diff;
            if (mid < sum_a_attack) break;
        }

        if (mid < sum_a_attack) left = mid;
        else right = mid;
    }
    cout << right << endl;
    return 0;
}