满分解法（100 分）

最后一次攻击与前面的攻击不同

如果一次攻击没有击败恶龙，攻击后的生命值是原生命值减去 $atk_i$、再加上 $d_i$，所以净减少量为 $atk_i-d_i$。然而，最后一次攻击不会触发恢复，只需它的攻击值足以覆盖剩余生命值。

这意味着不能简单地按净伤害从大到小依次攻击。例如，初始生命值为 $250$，两个头的 $(atk,d)$ 分别为 $(200,100)$ 和 $(100,1)$。前者净伤害为 $100$，后者为 $99$。先攻击前者时，生命值变成 $150$，后者不能击败它；先攻击后者时，生命值变成 $151$，再攻击前者即可击败。净伤害更大的头，反而应该留到最后。

因此先固定最后攻击的头，再决定前面需要哪些攻击。

哪些攻击可以出现在最后一击之前

考虑一次非致命攻击，如果 $atk_i-d_i\le 0$，它会使生命值不变或增加。删掉这次攻击后，继续尝试原来的后续攻击，恶龙的生命值不会比原方案更高：若某次提前击败，攻击次数更少；否则每次仍存活时，两种方案的生命值都减去同一个净伤害，大小关系保持。

于是，最优方案的前置攻击都可以选成正净伤害。这个结论不能用于删除最后一击的候选头：某个头即使回血很多，也可能凭借较大的 $atk_i$ 完成致命攻击，而这时回血根本不会发生。

设固定的最后一击为 $i$，前置攻击选择集合为 $S$。如果这些攻击直到最后一击前都未击败恶龙，那么最后一击成功的条件是

$$\sum_{j\in S}(atk_j-d_j)+atk_i\ge h,\qquad i\notin S.$$

若执行前置攻击时已经提前击败，只会用更少的次数，不会破坏我们对可行性的判断。

固定最后一击，优先选择最大的净伤害

固定前置攻击的个数。如果选中了净伤害较小的头，却没有选择另一个净伤害更大的头，把前者换成后者后，总净伤害不会减少，最后一击仍然可行。反复交换，便得到其余头中净伤害最大的若干个头。

因此，对每个最后一击，只需按净伤害降序取其他头，找到第一次满足条件的位置。直接为每个候选扫描一遍，最坏需要 $O(n^2)$ 时间。下一步用一次排序和前缀和避免重复累加。

在同一个前缀中排除最后攻击的头

令 $g_j=\max(0,atk_j-d_j)$，将所有头按 $g_j$ 降序排列。这里只把非正净伤害记成零以便统一求和，并没有把它们当作有用的前置攻击。以下使用排序后的下标 $0,1,\ldots,n-1$，每个位置同时保留该头的攻击值。

定义 $P_k$ 为前 $k$ 个头的 $g$ 之和，即

$$P_0=0,\qquad P_k=\sum_{j=0}^{k-1}g_j.$$

固定最后攻击的头 $i$。在前 $k$ 个位置中选准备攻击时，必须排除 $i$ 本身，否则同一个头会被计算两次。记 $[i<k]$ 为条件成立时取 $1$、否则取 $0$ 的指示量，则

$$F_i(k)=P_k-[i<k]g_i+atk_i$$

就是这些前置净伤害与最后攻击值之和。与它对应的攻击次数为

$$C_i(k)=k-[i<k]+1.$$

前面的例子中，排序后两个净伤害为 $100,99$。固定第 $0$ 个头作最后一击，取 $k=1$ 时需要排除它自身，只剩最后攻击值 $200$，还不够；取 $k=2$ 时，总贡献为 $100+99-100+200=299$，攻击次数为 $2-1+1=2$，恰好表示先攻击另一个头、再攻击它。

二分第一个可行前缀

从 $k$ 增加到 $k+1$ 时，如果新增的位置不是 $i$，$F_i$ 增加一个非负的 $g$；如果新增位置正是 $i$，该项立即被排除，$F_i$ 不变。所以判定 $F_i(k)\ge h$ 随 $k$ 单调不减。

在 $[0,n]$ 内二分最小可行的 $k$。如果不存在，就说明这个头不能作为最后一击。否则用 $C_i(k)$ 更新答案。二分结束得到的边界若为 $n+1$，只表示无可行前缀，不能据此访问前缀和。

当 $atk_i\ge h$ 且 $h>0$ 时，直接攻击即可，答案为 $1$。其余情况都有 $atk_i<h$，必须依靠正净伤害使判定变真。排序后所有零收益都在尾部，进入零收益尾部以后 $F_i$ 不再增加，所以第一个可行前缀不会额外纳入这些无益位置。这样，$C_i(k)$ 不会因为把负净伤害截成零而多算无用攻击。

净伤害相同的头可以任意排列。排除操作针对的是当前头的具体位置，而不是删除所有与它净伤害相同的头。

为什么最终答案最小

每个通过判定的候选都能在不超过其计数的攻击次数内击败恶龙：要么前置攻击已经击败，要么最后一击成功。因此真实最优次数不大于算法输出的最小候选次数。

反过来，取一个真实最优方案，设它最后攻击的头为 $i$，总共攻击 $t$ 次。删去非正净伤害的前置攻击不会更差，因此可认为它的前 $t-1$ 次攻击都有正净伤害。把它们替换为除 $i$ 外净伤害最大的 $t-1$ 个头，总贡献不会减少。枚举到 $i$ 时，二分得到的可行前缀所包含的其他头不超过 $t-1$ 个，所以算法给出的候选次数不大于 $t$。两个方向结合，算法得到的正是最少攻击次数。

若所有候选都不可行，就不存在任何成功方案，输出 No。初始 $h=0$ 时，恶龙已经被击败，单独输出 Yes 和 $0$。

复杂度

时间复杂度 $O(n\log n)$：排序需要 $O(n\log n)$，建立前缀和需要 $O(n)$，每个头进行一次 $O(\log n)$ 的二分。

空间复杂度 $O(n)$：保存各个头的信息及前缀和。

AC 代码（C++20）

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

void solve() {
  int n;
  i64 h;
  cin >> n >> h;
  vector<pair<i64, i64>> a(n);
  for (auto& [gain, atk] : a) {
    i64 d;
    cin >> atk >> d;
    gain = max(0LL, atk - d);
  }
  if (h == 0) {
    cout << "Yes\n0\n";
    return;
  }
  sort(a.rbegin(), a.rend());
  vector<i64> pre(n + 1);
  for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i].first;
  int ans = n + 1;
  for (int i = 0; i < n; i++) {
    auto [gain, atk] = a[i];
    if (atk >= h) {
      cout << "Yes\n1\n";
      return;
    }
    auto check = [&](int cnt) {
      return pre[cnt] - (i < cnt ? gain : 0) + atk >= h;
    };
    int lo = 0, hi = n;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (check(mid)) hi = mid - 1;
      else lo = mid + 1;
    }
    if (lo <= n) ans = min(ans, lo - (i < lo) + 1);
  }
  if (ans <= n) cout << "Yes\n" << ans << '\n';
  else cout << "No\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

利用两类特殊性质（通过子任务 3–4，共 20 分）

两类特殊性质都只需考虑零次或一次

先处理 $h=0$：初始生命值已经为零，最少攻击次数为 $0$。下文考虑 $h>0$。

若存在一个头满足 $atk_i\ge h$，第一次就攻击这个头即可使生命值变为零，并且不触发恢复。由于初始生命值为正，不可能零次击败，所以最少次数恰为 $1$。这覆盖子任务 $4$。

再考虑子任务 $3$，其中每个头都满足 $atk_i\le d_i$。如果一次攻击没有击败恶龙，攻击后的生命值为原生命值加上 $d_i-atk_i$，不会减少。因而只要一开始所有头都不能直接击败，之后的生命值也不会低于初始值，任何头都不可能成为致命一击，答案为 No。否则仍然只需一次攻击。

所以只需读入时记录最大的 $atk_i$：先判断初始零血，再判断最大攻击值是否至少为 $h$。这份方法只保证上述两类特殊性质，不能处理一般情况下靠多次净伤害累积而击败的方案，覆盖子任务 $3,4$，合计 $20$ 分。

时间复杂度 $O(n)$，只扫描一次输入。

空间复杂度 $O(1)$，无需保存每个头的信息。

参考代码（C++20）

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

void solve() {
  int n;
  i64 h;
  cin >> n >> h;
  i64 max_atk = 0;
  for (int i = 0; i < n; i++) {
    i64 atk, d;
    cin >> atk >> d;
    max_atk = max(max_atk, atk);
  }
  if (h == 0) cout << "Yes\n0\n";
  else if (max_atk >= h) cout << "Yes\n1\n";
  else cout << "No\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

枚举最后一击并逐个累加（通过子任务 1–4，共 70 分）

先固定不回血的最后一击

最后一击只需要攻击值足够大，而之前的非致命攻击会产生 $atk_j-d_j$ 的净伤害。一个非致命攻击若净伤害非正，删掉它后，生命值不会更高，之后的攻击仍能在相同或更少的次数内击败恶龙。因此它不需要出现在最后一击之前，但仍可以是最后一击本身。

先把所有头按净伤害降序排列。枚举最后攻击的头 $i$，令当前累计贡献为 $atk_i$、次数为 $1$。从排序序列开头扫描，跳过 $i$，并且只取净伤害为正的头；每取一个头，就加入它的净伤害并增加一次攻击。当累计贡献达到 $h$ 时记录当前次数。若正净伤害已经用完仍不够，则该最后一击不可行。

固定前置攻击个数时，选最大的净伤害能使总贡献最大：若选中较小项而漏掉较大项，交换后可行性不会变差。因而上述扫描为每个最后一击找到了最少的准备攻击次数。即使准备阶段提前击败，得到的实际次数只会更少；枚举到真正最后攻击的头时，这个更早结束的方案也会被考虑。最后对所有候选次数取最小值，无可行候选则输出 No。

覆盖的限制与特殊分支

首先处理 $h=0$，答案为 $0$。再求最大攻击值；若它至少为 $h$，则一次攻击已经足够，直接输出 $1$。

对于子任务 $1,2$，$n\le 2000$，可以接受最坏二次扫描。对于子任务 $3$，所有 $atk_i\le d_i$，没有正净伤害；若不能直接击败，每次内层扫描都会立即停止。对于子任务 $4$，存在足以直接击败的头，前面的最大值判断已经结束程序。因此这份方法覆盖子任务 $1,2,3,4$，合计 $70$ 分。

时间复杂度 $O(n^2)$，这是一般输入的最坏界。子任务 $3$ 只需排序及线性枚举，为 $O(n\log n)$；子任务 $4$ 在读入后立即判断，为 $O(n)$。

空间复杂度 $O(n)$。

参考代码（C++20）

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

void solve() {
  int n;
  i64 h;
  cin >> n >> h;
  vector<pair<i64, i64>> a(n);
  i64 max_atk = 0;
  for (auto& [gain, atk] : a) {
    i64 d;
    cin >> atk >> d;
    gain = atk - d;
    max_atk = max(max_atk, atk);
  }
  if (h == 0) {
    cout << "Yes\n0\n";
    return;
  }
  if (max_atk >= h) {
    cout << "Yes\n1\n";
    return;
  }
  sort(a.rbegin(), a.rend());
  int ans = n + 1;
  for (int i = 0; i < n; i++) {
    i64 sum = a[i].second;
    int cnt = 1;
    for (int j = 0; j < n && sum < h; j++) {
      if (a[j].first <= 0) break;
      if (i == j) continue;
      sum += a[j].first;
      cnt++;
    }
    if (sum >= h) ans = min(ans, cnt);
  }
  if (ans <= n) cout << "Yes\n" << ans << '\n';
  else cout << "No\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}