USACO 2014 December Contest, Silver Problem 3. Cow Jog

原題下載

USACO2014-DEC-S3

答案

(Analysis by Jonathan Paulson - jonathanpaulson@gmail.com)

If the cows didn't have to slow down, after TT seconds cow ii will be at position xi+T?sixi+T?si. If a faster cow started behind a slower cow, but the faster cow ended up ahead, that means the faster cow will join the slower cow's group (or a group in the middle).

So we want to count the number of cows don't "cross" any cows ahead of them; this is the number of cows who won't join another group (and hence will start their own group).

The most obvious way to to go through each cow and check if any of the cows ahead of them are going to end up behind them. But this is too slow: there are O(N^2) pairs of cows, and N = 10^5. So O(N^2) ~ 10^10, and computers only do about 10^9 operations per second.

Luckily, there is a faster way: start from the back, and keep track of the least far ending position as you go. This only takes about N operations, which is very fast.

Here is my code for the fast approach:

#include <cstdio>
#include <vector>

#define PB push_back

using namespace std;

typedef long long ll;

int main() {
  ll n, t;
  scanf("%lld %lld", &n, &t);
  vector<ll> S;
  for(ll i=0; i<n; i++) {
    ll x, s;
    scanf("%lld %lld\n", &x, &s);
    S.PB(x + s*t);
  }

  ll ans = 1;
  ll slow = S[n-1];
  for(ll i=n-1; i>=0; i--) {
    if(S[i] < slow) { ans++; }
    slow = min(slow, S[i]);
  }
  printf("%lld\n", ans);
}

以上就是關(guān)于【USACO 2014 December Contest, Silver Problem 3. Cow Jog】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動(dòng)：留學(xué)申請(qǐng)的“核武器”來了！

耗時(shí)一年備考 USACO 卻毫無收獲？一文教你找準(zhǔn)最佳備考起步時(shí)間！