USACO 2015 US Open, Silver Problem 2. Trapped in the Haybales (Silver)

原題下載

USACO2015OPEN-S2

答案

(Analysis by Nick Wu).

If we pick a bale that we want to add hay to, then we can guarantee that Bessie cannot break through that bale. Therefore, once we have picked the bale, we can simulate in linear time whether Bessie can still escape by having her keep on breaking bales until she reaches one that she cannot break, and our chosen bale. If she can escape, then the bale we have selected doesn't work.

However, this gives us an?O(N2)?algorithm which is too slow.

To speed things up, let haybale?K?be the rightmost haybale that is to the left of Bessie's starting place, and start simulating this process where haybale?K?is the one we want to add hay to, keeping track of the rightmost bale that Bessie breaks. If we then select haybale?K?1?as the bale to add hay to, we already know that Bessie can reach the rightmost haybale as mentioned above. If we sweep over the haybales from right-to-left, and keep track of the rightmost haybale, then we note that we do at most a linear amount of work. After sorting the haybales in?O(NlogN), we can do this in linear time. We do the same thing for the haybales to the right of Bessie, so the whole process is?O(N)?after sorting.

Here is Mark Gordon's code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

#define INF 1000000010

int main() {
  freopen("trapped.in", "r", stdin);
  freopen("trapped.out", "w", stdout);

  int N, B;
  cin >> N >> B;
  vector<pair<int, int> > A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i].second >> A[i].first;
  }
  sort(A.begin(), A.end());

  int result = INF;
  int sp = lower_bound(A.begin(), A.end(), make_pair(B, 0)) - A.begin();

  int j = sp;
  for (int i = sp - 1; i >= 0; i--) {
    while (j < N && A[j].first <= A[i].first + A[i].second) {
      result = min(result, A[j].first - A[i].first - A[j].second);
      j++;
    }
  }

  j = sp - 1;
  for (int i = sp; i < N; i++) {
    while (j >= 0 && A[i].first - A[i].second <= A[j].first) {
      result = min(result, A[i].first - A[j].first - A[j].second);
      j--;
    }
  }

  if (result == INF) {
    cout << -1 << endl;
  } else {
    cout << max(result, 0) << endl;
  }
  return 0;
}

以上就是關于【USACO 2015 US Open, Silver Problem 2. Trapped in the Haybales (Silver)】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

2026理工科競賽“大洗牌”：線上考試終結、報名門檻收緊、晉級規則重塑...你準備好了嗎？