USACO 2016 January Contest, Gold Problem 1. Angry Cows

原題下載

USACO2016-JAN-G1

答案

(Analysis by Brian Dean)

One approach for solving this problem is by combining a left-to-right scan with a right-to-left scan (one could call each scan either greedy or an example of dynamic programming). We first run a greedy/DP algorithm from left to right to determine for each hay bale the minimum power with which it must explode in order to propagate all the way left. We then do the same from right to left, computing for each hay bale the minimum power with which it must explode in order to propagate all the way to the right. Finally, by scanning through the list of hay bales, we can use these two numbers to identify the best "crossover" point where we should set the initial explosion.

Here is Mark Gordon's remarkably concise solution. Note how he uses a couple of clever tricks -- for example to run the algorithm from right to left, he simply reverses the input, runs the left-to-right algorithm, then reverses the output so it appears in the forward direction. Note also how he multiplies all haybale locations by 2 initially so only integer math is required; this eliminates any possibility of rounding error from using floating point numbers. This is why, for example, Mark uses "2 + max(..." in his final loop, since it would normally be "1 +" but the numbers are still scaled up by 2.

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

using namespace std;

#define INF 2000000000

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

  int N; cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] *= 2;
  }
  sort(A.begin(), A.end());
  A.resize(unique(A.begin(), A.end()) - A.begin());

  vector<int> DP[2];
  for (int it = 0; it < 2; it++) {
    int lstj = 0;
    DP[it].resize(N, INF);
    DP[it][0] = -2;
    for (int i = 1; i < N; i++) {
      while (lstj + 1 < i && abs(A[i] - A[lstj + 1]) > DP[it][lstj + 1] + 2) {
        lstj++;
      }
      DP[it][i] = min(abs(A[i] - A[lstj]), DP[it][lstj + 1] + 2);
    }
    reverse(A.begin(), A.end());
  }
  reverse(DP[1].begin(), DP[1].end());

  int i = 0;
  int j = N - 1;
  int result = INF;
  while (i < j) {
    result = min(result, max((A[j] - A[i]) / 2, 2 + max(DP[0][i], DP[1][j])));
    if (DP[0][i + 1] < DP[1][j - 1]) {
      i++;
    } else {
      j--;
    }
  }
  cout << result / 2 << '.' << (result % 2 ? 5 : 0) << '\n';

  return 0;
}

Another (slightly slower, but still feasible) solution approach is illustrated by the following code by Nick Wu. It essentially does a binary search on the size of the first explosion. To test if a particular initial explosion size works, it then does a binary search for the location of the initial explosion.

import java.io.*;
import java.util.*;
public class angryGloglog {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("angry.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("angry.out")));

		int n = Integer.parseInt(br.readLine());
		TreeSet<Long> set = new TreeSet<Long>();
		for(int i = 0; i < n; i++) {
			set.add(2L*Integer.parseInt(br.readLine()));
		}

		long min = 0;
		long max = 1000000000;
		while(min != max) {
			long mid = (min+max)/2;
			long l = set.first();
			long r = set.last();
			while(l < r) {
				long m = (l+r+1)/2;
				if(possibleFirst(set, m, mid)) {
					l = m;
				}
				else {
					r = m-1;
				}
			}
			if(possibleLast(set, l, mid)) {
				max = mid;
			}
			else {
				min = mid+1;
			}
		}
		
		pw.printf("%.1f\n", min / 2.0);
		pw.close();
	}

	public static boolean possibleFirst(TreeSet<Long> set, long start, long r) {
		if(set.first() < start - r) {
			long curr = set.ceiling(start - r);
			long currRadius = r-2;
			while(curr != set.first()) {
				long next = set.ceiling(curr - currRadius);
				if(next >= curr) {
					return false;
				}
				curr = next;
				currRadius-=2;
			}
		}
		return true;
	}
	
	public static boolean possibleLast(TreeSet<Long> set, long start, long r) {
		if(set.last() > start + r) {
			long curr = set.floor(start + r);
			long currRadius = r-2;
			while(curr != set.last()) {
				long next = set.floor(curr + currRadius);
				if(next <= curr) {
					return false;
				}
				curr = next;
				currRadius-=2;
			}
		}
		return true;
	}

}

以上就是關于【USACO 2016 January Contest, Gold Problem 1. Angry Cows】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動章程出爐：新規則必看！

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