USACO 2015 January Contest, Silver Problem 1. Stampede

原题下载

USACO2015JAN-S1

答案

(Analysis by Mark Gordon)

The first observation to make in this problem is that we can transform each cow into a time interval corresponding to the interval that the cow is on the line x=0.

Viewed this way the problem can be solved using a sweep line technique. Simply create a sorted list of events corresponding to the times that a cow's interval begins and ends. Every time a cow's interval begins insert it into a set and when it ends remove it from the set. Then to solve the problem we simply need to keep track of which cows in the set ever have the minimum y-coordinate among cows in the set.

See my code for a sample implementation

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

using namespace std;

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

  int N;
  cin >> N;

  vector<pair<int, int> > events;
  for (int i = 0; i < N; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    x *= -r;

    /* We'll use a negative y value to indicate the end of an interval. */
    events.push_back(make_pair(x - r, y));
    events.push_back(make_pair(x, -y));
  }
  sort(events.begin(), events.end());

  set<int> seen; /* Tracks which intervals we've seen. */
  set<int> active; /* Tracks which intervals are currently above us. */
  for (int i = 0; i < events.size(); ) {
    /* Add/remove any intervals that begin/end at time events[i].first. */
    int j;
    for (j = i; j < events.size() && events[i].first == events[j].first; j++) {
      int y = events[j].second;
      if (y > 0) {
        active.insert(y);
      } else {
        active.erase(-y);
      }
    }

    /* Add the first interval we can see to our list of seen intervals. */
    if (!active.empty()) {
      seen.insert(*active.begin());
    }

    i = j;
  }
  cout << seen.size() << endl;

  return 0;
}

There was also a fairly different approach to this problem that could be coded fairly succinctly using STL's set. We simply store all "interesting" times (times immediate before/during/after an interval starts and ends) in a set and then process the intervals in increasing y values. Using set's lower_bound and upper_bound functions we can find the iterator range representing all times within that interval. If the interval is non-empty we delete everything in the range and increment the number of seen intervals, otherwise the interval is not visible.

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

using namespace std;

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

  int N;
  cin >> N;

  set<int> st;
  vector<pair<int, pair<int, int> > > A;
  for (int i = 0; i < N; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    x *= -r;
    A.push_back(make_pair(y, make_pair(x - r, x)));
    st.insert(x - r - 1);
    st.insert(x - r);
    st.insert(x - r + 1);
    st.insert(x - 1);
    st.insert(x);
    st.insert(x + 1);
  }
  sort(A.begin(), A.end());

  int result = 0;
  for (int i = 0; i < A.size(); i++) {
    auto it = st.lower_bound(A[i].second.first);
    auto jt = st.lower_bound(A[i].second.second);
    if (it != jt) {
      ++result;
      st.erase(it, jt);
    }
  }
  cout << result << endl;

  return 0;
}

翰林USACO课程体系流程图

 

以上就是关于【USACO 2015 January Contest, Silver Problem 1. Stampede】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！