USACO 2014 December Contest, Gold Problem 3. Cow Jog

原题下载

USACO2014-DEC-G3

答案

(Analysis by Mark Gordon)

Two cows must be in different lanes if one cow overtakes the other at some point (or at the very end) in the jog. Viewed this way we can greedily assign all cows that are not overtaken by another cow during the jog to lane 1. We can then remove these cows and repeat the algorithm to assign cows to the remaining lanes.

To prove this is optimal suppose we assign k lanes in total; then there is some cow, c_k, in lane k that is overtaken during the jog by a cow in lane k−1, c_k−1 (otherwise we would have assigned it to lane k−1(instead). We can repeat this and find c_k−2 as the cow that overtakes c_k−1 in lane k-2 all the way down to c₁. Crucially, because the overtakes relation is transitive, it follows that c_i overtakes c_j for i<j. Therefore none of these cows can be in the same lane and k lanes are therefore required (and the greedy algorithm mentioned achieves this).

Efficiently implementing a solution based on this can be done in a number of ways. One way is to realize that the end positions of the cows in cc are non-increasing while the start positions are increasing. Therefore we can simply compute the longest non-increasing subsequence of the array. This is a small adaptation of the well known Longest Increasing Subsequence algorithm.

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

using namespace std;

int main() {
  int N, T;
  cin >> N >> T;

  vector<long long> A;
  for (int i = 0; i < N; i++) {
    long long x, s;
    cin >> x >> s;
    x = -(x + s * T);

    if (A.empty() || x >= A.back()) {
      A.push_back(x);
    } else {
      *upper_bound(A.begin(), A.end(), x) = x;
    }
  }

  cout << A.size() << endl;
  return 0;
}