[USACO15OPEN]Trapped in the Haybales G 题解

LiveZoom · 2022-08-16 21:57:35 · 题解

Description

给你 n 个干草捆，把这条路分成了 n-1 个区间，问你从多少个点开始走，能够成功逃脱。

Solution

先按坐标排序，显然在两个干草捆之间的所有点要么都能逃脱，要么都不能逃脱，所以可以枚举区间然后暴力去跑，这样是 O(n^2) 的，有 79 分的好成绩。

考虑优化，还是枚举区间，定义数组 t 表示这个区间是否能逃出去。也就是说当 t_i 等于 1 时，代表这个区间可以逃出去，否则逃不出去。那么我们暴力跑到一个点 x 时，如果 t_x 已经被标记为 1 了，那么就可以判断出可以跑出去，并把当前区间标记为 1。否则就一直暴力走，直到能够直接判断走不出去。大概是 O(n\log n) 的。

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#define db(x) cerr << #x << '=' << x << endl;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define dbg debug("*** Passing [%s] in LINE %d\n", __FUNCTION__, __LINE__)

using namespace std;

const int kMaxN = 1e5 + 5;

struct Node {
  int s, p;

  friend bool operator < (const Node& n1, const Node& n2) {
    return n1.p < n2.p;
  }
} a[kMaxN];

int n, ans;
int s[kMaxN], p[kMaxN];
bool tra[kMaxN];

bool check(int x) {
  int l = x, r = x + 1;
  for (; l && r <= n; ) {
    int nw = p[r] - p[l];
    if (nw <= s[l] && nw <= s[r]) {
      return 0;
    }    
    if (nw > s[l]) {
      --l;
      if (!l || tra[l]) {
        return tra[x] = 1;
      }
    }
    if (nw > s[r]) {
      ++r;
      if (r > n || tra[r - 1]) {
        return tra[x] = 1;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].s >> a[i].p;
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i) {
    s[i] = a[i].s, p[i] = a[i].p;
  }
  tra[0] = tra[n] = 1;
  for (int i = 1; i < n; ++i) {
    if (!check(i)) {
      ans += p[i + 1] - p[i];
    }
  }
  cout << ans << endl;
  return 0;
}