题解：CF2037D Sharky Surfing

O_v_O · 2024-11-24 12:10:40 · 题解

题意

有 n 个障碍区间，你不可以跳到障碍区间的任意一个点上（区间不会重叠），有 m 个跳跃提升药水，每个药水在 x_i 上，你喝了这瓶药水会获得 v_i 的跳跃提升（你可以不喝），初始跳跃能力为 1，你需要求出你最少要喝多少瓶药水才能跨过所有的障碍区间。

思路

如果本体只有一个障碍区间，从贪心角度来看，我们肯定喝那些对跳跃能力提升大的药水，然后在喝小些的，直到跳跃能力可以跳过这个障碍区间为止。

再看这道题，由于有多个障碍区间，那么我们就用一个优先队列来维护药水值，然后在每次遇到障碍时，我们就判断当前的跳跃能力是否可以跳过去，如果不可以，就从优先队列里去最大的药水喝，直到能力够了为止，如果所有药水都喝了还跳不过去，那么就无法抵达终点，输出 -1。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int t, n, m, l;
pair<int, int> a[N], b[N];

void solve() {
  cin >> n >> m >> l;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i].first >> b[i].second;
  }
  priority_queue<int> q;
  int sum = 1, cnt = 0;
  for (int i = 1, j = 1; i <= n; i++) {
    while (j <= m && b[j].first < a[i].first) {
      q.push(b[j++].second);
    }
    while (!q.empty() && sum <= a[i].second - a[i].first + 1) {
      sum += q.top();
      cnt++;
      q.pop();
    }
    if (sum <= a[i].second - a[i].first + 1) {
      cout << -1 << '\n';
      return;
    }
  }
  cout << cnt << '\n';
}

int main() {
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}