USACO 2015 December Contest, Gold Problem 1. High Card Low Card (Gold)

原题下载

USACO2015-DEC-G1

答案

(Analysis by Nathan Pinsker)

This problem seems daunting at first, but a few insights can give way to a greedy strategy for solving it:

- You're free to mentally rearrange Elsie's cards however you like within each half, since you know what she's going to play, and you can simply "match" your cards to hers.

- It's always best to use your N/2 highest cards in the first half, and your N/2 lowest cards in the second half. This means we can consider both halves completely independently, since we know which cards are going to be played in each.

(For the remainder of the analysis, we'll only consider the first half -- the second half can be analyzed with very similar arguments.)

- If you're aiming for X points, then you should always aim to beat Elsie's X lowest cards. This is because, if Bessie can beat some set made of X of Elsie's cards, then you can always swap Elsie's cards for lower cards without losing any points.

- If you want to beat one of Elsie's cards, you should always do it with the lowest possible card you can do it with. After all, having a higher card in your hand is strictly better than having a lower card in your hand.

This hints at a greedy solution: for each of Elsie's cards in ascending order, find the lowest possible card you have that beats it, play that card against hers, and try to beat the next one. Some thinking can convince you that this is the best possible solution, since it's the "lexicographically lowest" -- intuitively, each card played so far is the minimum possible card you could have played, so you'll have the maximum possible number of high cards available for you to use.

Here is Mark Gordon's solution, which uses a pair of sweeps through each of the arrays to implement this idea:

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

using namespace std;

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

  ios_base::sync_with_stdio(false);
  int N; cin >> N;

  vector<bool> used(2 * N);
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i]--;
    used[A[i]] = true;
  }
  sort(A.begin(), A.begin() + N / 2);
  sort(A.begin() + N / 2, A.end());
  rotate(A.begin(), A.begin() + N / 2, A.end());

  vector<int> B;
  for (int i = 0; i < 2 * N; i++) {
    if (!used[i]) {
      B.push_back(i);
    }
  }

  int res = 0;
  for (int i = N / 2, j = N / 2; i < N; i++, j++, res++) {
    while (j < N && B[j] < A[i]) {
      j++;
    }
    if (j == N) {
      break;
    }
  }
  for (int i = N / 2 - 1, j = N / 2 - 1; i >= 0; i--, j--, res++) {
    while (j >= 0 && B[j] > A[i]) {
      j--;
    }
    if (j == -1) {
      break;
    }
  }
  cout << res << endl;

  return 0;
}